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 180549 : static int status_in(isl_int *ineq, struct isl_tab *tab)
46 : {
47 180549 : enum isl_ineq_type type = isl_tab_ineq_type(tab, ineq);
48 180549 : switch (type) {
49 : default:
50 0 : case isl_ineq_error: return STATUS_ERROR;
51 95633 : case isl_ineq_redundant: return STATUS_VALID;
52 19554 : case isl_ineq_separate: return STATUS_SEPARATE;
53 43784 : case isl_ineq_cut: return STATUS_CUT;
54 958 : case isl_ineq_adj_eq: return STATUS_ADJ_EQ;
55 20620 : 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 16721 : static int *eq_status_in(__isl_keep isl_basic_map *bmap_i,
66 : struct isl_tab *tab_j)
67 : {
68 : int k, l;
69 16721 : int *eq = isl_calloc_array(bmap_i->ctx, int, 2 * bmap_i->n_eq);
70 : unsigned dim;
71 :
72 16721 : if (!eq)
73 0 : return NULL;
74 :
75 16721 : dim = isl_basic_map_total_dim(bmap_i);
76 19897 : for (k = 0; k < bmap_i->n_eq; ++k) {
77 9528 : for (l = 0; l < 2; ++l) {
78 6352 : isl_seq_neg(bmap_i->eq[k], bmap_i->eq[k], 1+dim);
79 6352 : eq[2 * k + l] = status_in(bmap_i->eq[k], tab_j);
80 6352 : if (eq[2 * k + l] == STATUS_ERROR)
81 0 : goto error;
82 : }
83 : }
84 :
85 16721 : 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 34858 : 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 34858 : unsigned n_eq = bmap_i->n_eq;
100 34858 : int *ineq = isl_calloc_array(bmap_i->ctx, int, bmap_i->n_ineq);
101 :
102 34858 : if (!ineq)
103 0 : return NULL;
104 :
105 225513 : for (k = 0; k < bmap_i->n_ineq; ++k) {
106 209901 : if (tab_i && isl_tab_is_redundant(tab_i, n_eq + k)) {
107 40967 : ineq[k] = STATUS_REDUNDANT;
108 40967 : continue;
109 : }
110 168934 : ineq[k] = status_in(bmap_i->ineq[k], tab_j);
111 168934 : if (ineq[k] == STATUS_ERROR)
112 0 : goto error;
113 168934 : if (ineq[k] == STATUS_SEPARATE)
114 19246 : break;
115 : }
116 :
117 34858 : return ineq;
118 : error:
119 0 : free(ineq);
120 0 : return NULL;
121 : }
122 :
123 168424 : static int any(int *con, unsigned len, int status)
124 : {
125 : int i;
126 :
127 910595 : for (i = 0; i < len ; ++i)
128 771758 : if (con[i] == status)
129 29587 : return 1;
130 138837 : 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 983 : static int find(int *con, unsigned len, int status)
137 : {
138 : int i;
139 :
140 4523 : for (i = 0; i < len ; ++i)
141 4523 : if (con[i] == status)
142 983 : return i;
143 0 : return -1;
144 : }
145 :
146 14729 : static int count(int *con, unsigned len, int status)
147 : {
148 : int i;
149 14729 : int c = 0;
150 :
151 137210 : for (i = 0; i < len ; ++i)
152 122481 : if (con[i] == status)
153 18345 : c++;
154 14729 : return c;
155 : }
156 :
157 27917 : static int all(int *con, unsigned len, int status)
158 : {
159 : int i;
160 :
161 54990 : for (i = 0; i < len ; ++i) {
162 41044 : if (con[i] == STATUS_REDUNDANT)
163 2691 : continue;
164 38353 : if (con[i] != status)
165 13971 : return 0;
166 : }
167 13946 : 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 70165 : static int any_eq(struct isl_coalesce_info *info, int status)
207 : {
208 : unsigned n_eq;
209 :
210 70165 : n_eq = isl_basic_map_n_equality(info->bmap);
211 70165 : 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 97895 : static int any_ineq(struct isl_coalesce_info *info, int status)
219 : {
220 : unsigned n_ineq;
221 :
222 97895 : n_ineq = isl_basic_map_n_inequality(info->bmap);
223 97895 : 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 0 : static int find_eq(struct isl_coalesce_info *info, int status)
234 : {
235 : unsigned n_eq;
236 :
237 0 : n_eq = isl_basic_map_n_equality(info->bmap);
238 0 : 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 983 : static int find_ineq(struct isl_coalesce_info *info, int status)
247 : {
248 : unsigned n_ineq;
249 :
250 983 : n_ineq = isl_basic_map_n_inequality(info->bmap);
251 983 : 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 2444 : static int count_eq(struct isl_coalesce_info *info, int status)
259 : {
260 : unsigned n_eq;
261 :
262 2444 : n_eq = isl_basic_map_n_equality(info->bmap);
263 2444 : 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 12285 : static int count_ineq(struct isl_coalesce_info *info, int status)
271 : {
272 : unsigned n_ineq;
273 :
274 12285 : n_ineq = isl_basic_map_n_inequality(info->bmap);
275 12285 : 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 77 : static int all_valid_or_cut(struct isl_coalesce_info *info)
282 : {
283 : int i;
284 :
285 191 : for (i = 0; i < 2 * info->bmap->n_eq; ++i) {
286 114 : if (info->eq[i] == STATUS_REDUNDANT)
287 0 : continue;
288 114 : if (info->eq[i] == STATUS_VALID)
289 54 : continue;
290 60 : if (info->eq[i] == STATUS_CUT)
291 60 : continue;
292 0 : return 0;
293 : }
294 :
295 237 : for (i = 0; i < info->bmap->n_ineq; ++i) {
296 229 : if (info->ineq[i] == STATUS_REDUNDANT)
297 24 : continue;
298 205 : if (info->ineq[i] == STATUS_VALID)
299 77 : continue;
300 128 : if (info->ineq[i] == STATUS_CUT)
301 59 : continue;
302 69 : return 0;
303 : }
304 :
305 8 : 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 1580 : static int coalesce_info_set_hull_hash(struct isl_coalesce_info *info)
313 : {
314 : isl_basic_map *hull;
315 : unsigned n_div;
316 :
317 1580 : hull = isl_basic_map_copy(info->bmap);
318 1580 : hull = isl_basic_map_plain_affine_hull(hull);
319 1580 : n_div = isl_basic_map_dim(hull, isl_dim_div);
320 1580 : hull = isl_basic_map_drop_constraints_involving_dims(hull,
321 : isl_dim_div, 0, n_div);
322 1580 : info->hull_hash = isl_basic_map_get_hash(hull);
323 1580 : isl_basic_map_free(hull);
324 :
325 1580 : return hull ? 0 : -1;
326 : }
327 :
328 : /* Free all the allocated memory in an array
329 : * of "n" isl_coalesce_info elements.
330 : */
331 38 : static void clear_coalesce_info(int n, struct isl_coalesce_info *info)
332 : {
333 : int i;
334 :
335 38 : if (!info)
336 0 : return;
337 :
338 1618 : for (i = 0; i < n; ++i) {
339 1580 : isl_basic_map_free(info[i].bmap);
340 1580 : isl_tab_free(info[i].tab);
341 : }
342 :
343 38 : free(info);
344 : }
345 :
346 : /* Clear the memory associated to "info".
347 : */
348 2009 : static void clear(struct isl_coalesce_info *info)
349 : {
350 2009 : info->bmap = isl_basic_map_free(info->bmap);
351 2009 : isl_tab_free(info->tab);
352 2009 : info->tab = NULL;
353 2009 : }
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 1234 : static void drop(struct isl_coalesce_info *info)
360 : {
361 1234 : clear(info);
362 1234 : info->removed = 1;
363 1234 : }
364 :
365 : /* Exchange the information in "info1" with that in "info2".
366 : */
367 1 : static void exchange(struct isl_coalesce_info *info1,
368 : struct isl_coalesce_info *info2)
369 : {
370 : struct isl_coalesce_info info;
371 :
372 1 : info = *info1;
373 1 : *info1 = *info2;
374 1 : *info2 = info;
375 1 : }
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 0 : static enum isl_change invert_change(enum isl_change change)
398 : {
399 0 : 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 0 : return isl_change_drop_second;
406 : case isl_change_drop_second:
407 0 : return isl_change_drop_first;
408 : case isl_change_fuse:
409 0 : 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 1550 : 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 1550 : if (!bmap)
427 0 : return NULL;
428 :
429 1889 : for (k = 0; k < info->bmap->n_eq; ++k) {
430 677 : if (info->eq[2 * k] == STATUS_VALID &&
431 338 : info->eq[2 * k + 1] == STATUS_VALID) {
432 338 : l = isl_basic_map_alloc_equality(bmap);
433 338 : if (l < 0)
434 0 : return isl_basic_map_free(bmap);
435 338 : isl_seq_cpy(bmap->eq[l], info->bmap->eq[k], len);
436 1 : } else if (info->eq[2 * k] == STATUS_VALID) {
437 0 : l = isl_basic_map_alloc_inequality(bmap);
438 0 : if (l < 0)
439 0 : return isl_basic_map_free(bmap);
440 0 : isl_seq_neg(bmap->ineq[l], info->bmap->eq[k], len);
441 1 : } else if (info->eq[2 * k + 1] == STATUS_VALID) {
442 1 : l = isl_basic_map_alloc_inequality(bmap);
443 1 : if (l < 0)
444 0 : return isl_basic_map_free(bmap);
445 1 : isl_seq_cpy(bmap->ineq[l], info->bmap->eq[k], len);
446 : }
447 : }
448 :
449 16320 : for (k = 0; k < info->bmap->n_ineq; ++k) {
450 14770 : if (info->ineq[k] != STATUS_VALID)
451 4456 : continue;
452 10314 : l = isl_basic_map_alloc_inequality(bmap);
453 10314 : if (l < 0)
454 0 : return isl_basic_map_free(bmap);
455 10314 : isl_seq_cpy(bmap->ineq[l], info->bmap->ineq[k], len);
456 : }
457 :
458 1550 : 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 1 : 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 1 : n_old = 2 * info[i].bmap->n_eq + info[i].bmap->n_ineq;
472 1 : n_old += 2 * info[j].bmap->n_eq + info[j].bmap->n_ineq;
473 :
474 1 : n_new = 2 * bmap->n_eq;
475 8 : for (k = 0; k < bmap->n_ineq; ++k)
476 7 : if (!isl_tab_is_redundant(tab, bmap->n_eq + k))
477 4 : ++n_new;
478 :
479 1 : 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 777 : 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 777 : struct isl_basic_map *fused = NULL;
503 777 : struct isl_tab *fused_tab = NULL;
504 777 : unsigned total = isl_basic_map_total_dim(info[i].bmap);
505 777 : unsigned extra_rows = extra ? extra->n_row : 0;
506 : unsigned n_eq, n_ineq;
507 777 : int simplify = 0;
508 :
509 777 : if (j < i)
510 2 : return fuse(j, i, info, extra, detect_equalities, check_number);
511 :
512 775 : n_eq = info[i].bmap->n_eq + info[j].bmap->n_eq;
513 775 : n_ineq = info[i].bmap->n_ineq + info[j].bmap->n_ineq;
514 1550 : fused = isl_basic_map_alloc_space(isl_space_copy(info[i].bmap->dim),
515 1550 : info[i].bmap->n_div, n_eq, n_eq + n_ineq + extra_rows);
516 775 : fused = add_valid_constraints(fused, &info[i], 1 + total);
517 775 : fused = add_valid_constraints(fused, &info[j], 1 + total);
518 775 : if (!fused)
519 0 : goto error;
520 775 : if (ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_RATIONAL) &&
521 0 : ISL_F_ISSET(info[j].bmap, ISL_BASIC_MAP_RATIONAL))
522 0 : ISL_F_SET(fused, ISL_BASIC_MAP_RATIONAL);
523 :
524 826 : for (k = 0; k < info[i].bmap->n_div; ++k) {
525 51 : int l = isl_basic_map_alloc_div(fused);
526 51 : if (l < 0)
527 0 : goto error;
528 51 : if (isl_seq_eq(info[i].bmap->div[k], info[j].bmap->div[k],
529 : 1 + 1 + total)) {
530 51 : isl_seq_cpy(fused->div[l], info[i].bmap->div[k],
531 : 1 + 1 + total);
532 : } else {
533 0 : isl_int_set_si(fused->div[l][0], 0);
534 0 : simplify = 1;
535 : }
536 : }
537 :
538 781 : for (k = 0; k < extra_rows; ++k) {
539 6 : l = isl_basic_map_alloc_inequality(fused);
540 6 : if (l < 0)
541 0 : goto error;
542 6 : isl_seq_cpy(fused->ineq[l], extra->row[k], 1 + total);
543 : }
544 :
545 775 : if (detect_equalities)
546 0 : fused = isl_basic_map_detect_inequality_pairs(fused, NULL);
547 775 : fused = isl_basic_map_gauss(fused, NULL);
548 775 : if (simplify || info[j].simplify) {
549 0 : fused = isl_basic_map_simplify(fused);
550 0 : info[i].simplify = 0;
551 : }
552 775 : fused = isl_basic_map_finalize(fused);
553 :
554 775 : fused_tab = isl_tab_from_basic_map(fused, 0);
555 775 : if (isl_tab_detect_redundant(fused_tab) < 0)
556 0 : goto error;
557 :
558 776 : if (check_number &&
559 1 : 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 775 : clear(&info[i]);
566 775 : info[i].bmap = fused;
567 775 : info[i].tab = fused_tab;
568 775 : info[i].modified = 1;
569 775 : drop(&info[j]);
570 :
571 775 : 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 1175 : 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 1175 : unsigned n_eq = info[i].bmap->n_eq;
613 :
614 1175 : snap = isl_tab_snap(info[i].tab);
615 1175 : if (isl_tab_mark_rational(info[i].tab) < 0)
616 0 : return isl_change_error;
617 1175 : snap2 = isl_tab_snap(info[i].tab);
618 :
619 2500 : for (k = 0; k < info[i].bmap->n_ineq; ++k) {
620 2496 : if (info[i].ineq[k] != STATUS_CUT)
621 1304 : continue;
622 1192 : if (isl_tab_select_facet(info[i].tab, n_eq + k) < 0)
623 0 : return isl_change_error;
624 2670 : for (l = 0; l < info[j].bmap->n_ineq; ++l) {
625 : int stat;
626 2649 : if (info[j].ineq[l] != STATUS_CUT)
627 1419 : continue;
628 1230 : stat = status_in(info[j].bmap->ineq[l], info[i].tab);
629 1230 : if (stat < 0)
630 0 : return isl_change_error;
631 1230 : if (stat != STATUS_VALID)
632 1171 : break;
633 : }
634 1192 : if (isl_tab_rollback(info[i].tab, snap2) < 0)
635 0 : return isl_change_error;
636 1192 : if (l < info[j].bmap->n_ineq)
637 1171 : break;
638 : }
639 :
640 1175 : if (k < info[i].bmap->n_ineq) {
641 1171 : if (isl_tab_rollback(info[i].tab, snap) < 0)
642 0 : return isl_change_error;
643 1171 : return isl_change_none;
644 : }
645 4 : 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 912 : static isl_bool contains(struct isl_coalesce_info *info, struct isl_tab *tab)
655 : {
656 : int k;
657 : unsigned dim;
658 912 : isl_basic_map *bmap = info->bmap;
659 :
660 912 : dim = isl_basic_map_total_dim(bmap);
661 1056 : for (k = 0; k < bmap->n_eq; ++k) {
662 : int stat;
663 189 : isl_seq_neg(bmap->eq[k], bmap->eq[k], 1 + dim);
664 189 : stat = status_in(bmap->eq[k], tab);
665 189 : isl_seq_neg(bmap->eq[k], bmap->eq[k], 1 + dim);
666 189 : if (stat < 0)
667 0 : return isl_bool_error;
668 189 : if (stat != STATUS_VALID)
669 29 : return isl_bool_false;
670 160 : stat = status_in(bmap->eq[k], tab);
671 160 : if (stat < 0)
672 0 : return isl_bool_error;
673 160 : if (stat != STATUS_VALID)
674 16 : return isl_bool_false;
675 : }
676 :
677 3962 : for (k = 0; k < bmap->n_ineq; ++k) {
678 : int stat;
679 3931 : if (info->ineq[k] == STATUS_REDUNDANT)
680 247 : continue;
681 3684 : stat = status_in(bmap->ineq[k], tab);
682 3684 : if (stat < 0)
683 0 : return isl_bool_error;
684 3684 : if (stat != STATUS_VALID)
685 836 : return isl_bool_false;
686 : }
687 31 : 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 848 : 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 848 : unsigned n_eq = info[i].bmap->n_eq;
736 848 : unsigned total = isl_basic_map_total_dim(info[i].bmap);
737 : isl_stat r;
738 : isl_bool super;
739 :
740 848 : if (isl_tab_extend_cons(info[i].tab, 1 + info[j].bmap->n_ineq) < 0)
741 0 : return isl_change_error;
742 :
743 848 : k = find_ineq(&info[i], STATUS_ADJ_INEQ);
744 848 : 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 848 : snap = isl_tab_snap(info[i].tab);
750 :
751 848 : if (isl_tab_unrestrict(info[i].tab, n_eq + k) < 0)
752 0 : return isl_change_error;
753 :
754 848 : isl_seq_neg(info[i].bmap->ineq[k], info[i].bmap->ineq[k], 1 + total);
755 848 : isl_int_sub_ui(info[i].bmap->ineq[k][0], info[i].bmap->ineq[k][0], 1);
756 848 : r = isl_tab_add_ineq(info[i].tab, info[i].bmap->ineq[k]);
757 848 : isl_seq_neg(info[i].bmap->ineq[k], info[i].bmap->ineq[k], 1 + total);
758 848 : isl_int_sub_ui(info[i].bmap->ineq[k][0], info[i].bmap->ineq[k][0], 1);
759 848 : if (r < 0)
760 0 : return isl_change_error;
761 :
762 9299 : for (k = 0; k < info[j].bmap->n_ineq; ++k) {
763 8451 : if (info[j].ineq[k] != STATUS_VALID)
764 4061 : continue;
765 4390 : if (isl_tab_add_ineq(info[i].tab, info[j].bmap->ineq[k]) < 0)
766 0 : return isl_change_error;
767 : }
768 848 : if (isl_tab_detect_constants(info[i].tab) < 0)
769 0 : return isl_change_error;
770 :
771 848 : super = contains(&info[j], info[i].tab);
772 848 : if (super < 0)
773 0 : return isl_change_error;
774 848 : if (super)
775 1 : return fuse(i, j, info, NULL, 0, 0);
776 :
777 847 : if (isl_tab_rollback(info[i].tab, snap) < 0)
778 0 : return isl_change_error;
779 :
780 847 : 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 4717 : 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 4717 : count_i = count_ineq(&info[i], STATUS_ADJ_INEQ);
822 4717 : count_j = count_ineq(&info[j], STATUS_ADJ_INEQ);
823 :
824 4717 : if (count_i != 1 && count_j != 1)
825 1138 : return isl_change_none;
826 :
827 3579 : cut_i = any_eq(&info[i], STATUS_CUT) || any_ineq(&info[i], STATUS_CUT);
828 3579 : cut_j = any_eq(&info[j], STATUS_CUT) || any_ineq(&info[j], STATUS_CUT);
829 :
830 3579 : if (!cut_i && !cut_j && count_i == 1 && count_j == 1)
831 768 : return fuse(i, j, info, NULL, 0, 0);
832 :
833 2811 : if (count_i == 1 && !cut_i)
834 371 : return is_adj_ineq_extension(i, j, info);
835 :
836 2440 : if (count_j == 1 && !cut_j)
837 476 : return is_adj_ineq_extension(j, i, info);
838 :
839 1964 : 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 349 : static int not_unique_unit_row(__isl_keep isl_mat *T, int row)
851 : {
852 : int i, j;
853 349 : int len = T->n_col - 1;
854 :
855 349 : i = isl_seq_first_non_zero(T->row[row] + 1, len);
856 349 : if (i < 0)
857 30 : return 1;
858 333 : if (!isl_int_is_one(T->row[row][1 + i]) &&
859 14 : !isl_int_is_negone(T->row[row][1 + i]))
860 9 : return 1;
861 :
862 310 : j = isl_seq_first_non_zero(T->row[row] + 1 + i + 1, len - (i + 1));
863 310 : if (j >= 0)
864 9 : return 1;
865 :
866 1936 : for (j = 1; j < T->n_row; ++j) {
867 1699 : if (j == row)
868 258 : continue;
869 1441 : if (!isl_int_is_zero(T->row[j][1 + i]))
870 64 : return 1;
871 : }
872 :
873 237 : 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 200 : static isl_bool is_affected(__isl_keep isl_basic_map *bmap, int ineq,
882 : int *affected, int total)
883 : {
884 : int i;
885 :
886 827 : for (i = 0; i < total; ++i) {
887 755 : if (!affected[i])
888 490 : continue;
889 265 : if (!isl_int_is_zero(bmap->ineq[ineq][1 + i]))
890 128 : return isl_bool_true;
891 : }
892 :
893 72 : 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 128 : 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 128 : if (!v)
923 0 : return NULL;
924 :
925 128 : ctx = isl_vec_get_ctx(v);
926 128 : isl_seq_gcd(v->el + 1, v->size - 1, &ctx->normalize_gcd);
927 256 : if (isl_int_is_zero(ctx->normalize_gcd) ||
928 128 : isl_int_is_one(ctx->normalize_gcd)) {
929 122 : return v;
930 : }
931 :
932 6 : v = isl_vec_cow(v);
933 6 : if (!v)
934 0 : return NULL;
935 :
936 6 : isl_int_fdiv_r(v->el[0], v->el[0], ctx->normalize_gcd);
937 6 : if (isl_int_is_zero(v->el[0]))
938 2 : return v;
939 :
940 4 : if (isl_tab_extend_cons(info->tab, 1) < 0)
941 0 : return isl_vec_free(v);
942 :
943 4 : isl_int_sub(info->bmap->ineq[ineq][0],
944 : info->bmap->ineq[ineq][0], v->el[0]);
945 4 : r = isl_tab_add_ineq(info->tab, info->bmap->ineq[ineq]);
946 4 : isl_int_add(info->bmap->ineq[ineq][0],
947 : info->bmap->ineq[ineq][0], v->el[0]);
948 :
949 4 : if (r < 0)
950 0 : return isl_vec_free(v);
951 :
952 4 : 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 64 : 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 64 : isl_vec *v = NULL;
998 : isl_mat *T;
999 : int i;
1000 : int k;
1001 : int *affected;
1002 :
1003 64 : k = relaxed[l];
1004 64 : ctx = isl_basic_map_get_ctx(info->bmap);
1005 64 : total = isl_basic_map_total_dim(info->bmap);
1006 64 : isl_int_add_ui(info->bmap->ineq[k][0], info->bmap->ineq[k][0], 1);
1007 64 : T = isl_mat_sub_alloc6(ctx, info->bmap->ineq, k, 1, 0, 1 + total);
1008 64 : T = isl_mat_variable_compression(T, NULL);
1009 64 : isl_int_sub_ui(info->bmap->ineq[k][0], info->bmap->ineq[k][0], 1);
1010 64 : if (!T)
1011 0 : return isl_stat_error;
1012 64 : if (T->n_col == 0) {
1013 0 : isl_mat_free(T);
1014 0 : return isl_stat_ok;
1015 : }
1016 :
1017 64 : affected = isl_alloc_array(ctx, int, total);
1018 64 : if (!affected)
1019 0 : goto error;
1020 :
1021 413 : for (i = 0; i < total; ++i)
1022 349 : affected[i] = not_unique_unit_row(T, 1 + i);
1023 :
1024 428 : for (i = 0; i < info->bmap->n_ineq; ++i) {
1025 : isl_bool handle;
1026 364 : if (any(relaxed, n, i))
1027 71 : continue;
1028 293 : if (info->ineq[i] == STATUS_REDUNDANT)
1029 93 : continue;
1030 200 : handle = is_affected(info->bmap, i, affected, total);
1031 200 : if (handle < 0)
1032 0 : goto error;
1033 200 : if (!handle)
1034 72 : continue;
1035 128 : v = isl_vec_alloc(ctx, 1 + total);
1036 128 : if (!v)
1037 0 : goto error;
1038 128 : isl_seq_cpy(v->el, info->bmap->ineq[i], 1 + total);
1039 128 : v = isl_vec_mat_product(v, isl_mat_copy(T));
1040 128 : v = try_tightening(info, i, v);
1041 128 : isl_vec_free(v);
1042 128 : if (!v)
1043 0 : goto error;
1044 : }
1045 :
1046 64 : isl_mat_free(T);
1047 64 : free(affected);
1048 64 : 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 27 : 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 27 : info[i].bmap = isl_basic_map_cow(info[i].bmap);
1073 27 : if (!info[i].bmap)
1074 0 : return isl_change_error;
1075 27 : total = isl_basic_map_total_dim(info[i].bmap);
1076 30 : for (l = 0; l < info[i].bmap->n_div; ++l)
1077 6 : if (!isl_seq_eq(info[i].bmap->div[l],
1078 3 : info[j].bmap->div[l], 1 + 1 + total)) {
1079 0 : isl_int_set_si(info[i].bmap->div[l][0], 0);
1080 0 : info[i].simplify = 1;
1081 : }
1082 54 : for (l = 0; l < n; ++l)
1083 27 : isl_int_add_ui(info[i].bmap->ineq[relax[l]][0],
1084 : info[i].bmap->ineq[relax[l]][0], 1);
1085 27 : ISL_F_CLR(info[i].bmap, ISL_BASIC_MAP_NO_REDUNDANT);
1086 27 : ISL_F_SET(info[i].bmap, ISL_BASIC_MAP_FINAL);
1087 27 : drop(&info[j]);
1088 27 : info[i].modified = 1;
1089 27 : if (j < i)
1090 1 : exchange(&info[i], &info[j]);
1091 27 : 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 61 : 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 61 : unsigned n_eq = info[i].bmap->n_eq;
1145 :
1146 126 : for (l = 0; l < n; ++l)
1147 65 : if (isl_tab_is_equality(info[i].tab, n_eq + relax[l]))
1148 0 : return isl_change_none;
1149 :
1150 61 : snap = isl_tab_snap(info[i].tab);
1151 126 : for (l = 0; l < n; ++l)
1152 65 : if (isl_tab_relax(info[i].tab, n_eq + relax[l]) < 0)
1153 0 : return isl_change_error;
1154 252 : for (l = 0; l < n; ++l) {
1155 65 : if (!isl_tab_is_redundant(info[i].tab, n_eq + relax[l]))
1156 65 : continue;
1157 0 : if (isl_tab_rollback(info[i].tab, snap) < 0)
1158 0 : return isl_change_error;
1159 0 : return isl_change_none;
1160 : }
1161 61 : snap2 = isl_tab_snap(info[i].tab);
1162 182 : for (l = 0; l < n; ++l) {
1163 64 : if (isl_tab_rollback(info[i].tab, snap2) < 0)
1164 0 : return isl_change_error;
1165 64 : if (isl_tab_select_facet(info[i].tab, n_eq + relax[l]) < 0)
1166 0 : return isl_change_error;
1167 64 : if (tighten_on_relaxed_facet(&info[i], n, relax, l) < 0)
1168 0 : return isl_change_error;
1169 64 : super = contains(&info[j], info[i].tab);
1170 64 : if (super < 0)
1171 0 : return isl_change_error;
1172 64 : if (super)
1173 30 : continue;
1174 34 : if (isl_tab_rollback(info[i].tab, snap) < 0)
1175 0 : return isl_change_error;
1176 34 : return isl_change_none;
1177 : }
1178 :
1179 27 : if (isl_tab_rollback(info[i].tab, snap2) < 0)
1180 0 : return isl_change_error;
1181 27 : 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 254 : 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 254 : unsigned total = isl_basic_map_total_dim(info->bmap);
1207 :
1208 254 : isl_int_init(max_k);
1209 :
1210 511 : for (k = 0; k < info->bmap->n_eq; ++k) {
1211 402 : if (info->eq[2 * k] == STATUS_VALID &&
1212 145 : info->eq[2 * k + 1] == STATUS_VALID)
1213 78 : continue;
1214 179 : isl_seq_abs_max(info->bmap->eq[k] + 1, total, &max_k);
1215 179 : if (isl_int_abs_gt(max_k, wraps->max))
1216 2 : isl_int_set(wraps->max, max_k);
1217 : }
1218 :
1219 1822 : for (k = 0; k < info->bmap->n_ineq; ++k) {
1220 2588 : if (info->ineq[k] == STATUS_VALID ||
1221 1020 : info->ineq[k] == STATUS_REDUNDANT)
1222 1022 : continue;
1223 546 : isl_seq_abs_max(info->bmap->ineq[k] + 1, total, &max_k);
1224 546 : if (isl_int_abs_gt(max_k, wraps->max))
1225 210 : isl_int_set(wraps->max, max_k);
1226 : }
1227 :
1228 254 : isl_int_clear(max_k);
1229 :
1230 254 : 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 127 : 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 127 : wraps->bound = 0;
1245 127 : wraps->mat = mat;
1246 127 : if (!mat)
1247 0 : return isl_stat_error;
1248 127 : ctx = isl_mat_get_ctx(mat);
1249 127 : wraps->bound = isl_options_get_coalesce_bounded_wrapping(ctx);
1250 127 : if (!wraps->bound)
1251 0 : return isl_stat_ok;
1252 127 : isl_int_init(wraps->max);
1253 127 : isl_int_set_si(wraps->max, 0);
1254 127 : if (wraps_update_max(wraps, &info[i]) < 0)
1255 0 : return isl_stat_error;
1256 127 : if (wraps_update_max(wraps, &info[j]) < 0)
1257 0 : return isl_stat_error;
1258 :
1259 127 : return isl_stat_ok;
1260 : }
1261 :
1262 : /* Free the contents of the isl_wraps data structure.
1263 : */
1264 127 : static void wraps_free(struct isl_wraps *wraps)
1265 : {
1266 127 : isl_mat_free(wraps->mat);
1267 127 : if (wraps->bound)
1268 127 : isl_int_clear(wraps->max);
1269 127 : }
1270 :
1271 : /* Mark the wrapping as failed by resetting wraps->mat->n_row to zero.
1272 : */
1273 123 : static isl_stat wraps_mark_failed(struct isl_wraps *wraps)
1274 : {
1275 123 : wraps->mat->n_row = 0;
1276 123 : 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 91 : static int allow_wrap(struct isl_wraps *wraps, int row)
1285 : {
1286 : int i;
1287 :
1288 91 : if (!wraps->bound)
1289 0 : return 1;
1290 :
1291 707 : for (i = 1; i < wraps->mat->n_col; ++i)
1292 629 : if (isl_int_abs_gt(wraps->mat->row[row][i], wraps->max))
1293 13 : return 0;
1294 :
1295 78 : 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 192 : 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 192 : isl_seq_cpy(wraps->mat->row[w], bound, len);
1310 192 : if (negate) {
1311 30 : isl_seq_neg(wraps->mat->row[w + 1], ineq, len);
1312 30 : ineq = wraps->mat->row[w + 1];
1313 : }
1314 192 : if (!isl_set_wrap_facet(set, wraps->mat->row[w], ineq))
1315 0 : return -1;
1316 192 : if (isl_seq_eq(wraps->mat->row[w], bound, len))
1317 101 : return 0;
1318 91 : if (!allow_wrap(wraps, w))
1319 13 : return 0;
1320 78 : 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 177 : 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 177 : isl_basic_map *bmap = info->bmap;
1350 177 : unsigned len = 1 + isl_basic_map_total_dim(bmap);
1351 :
1352 177 : w = wraps->mat->n_row;
1353 :
1354 552 : for (l = 0; l < bmap->n_ineq; ++l) {
1355 790 : if (info->ineq[l] == STATUS_VALID ||
1356 304 : info->ineq[l] == STATUS_REDUNDANT)
1357 308 : continue;
1358 178 : if (isl_seq_is_neg(bound, bmap->ineq[l], len))
1359 19 : continue;
1360 159 : if (isl_seq_eq(bound, bmap->ineq[l], len))
1361 0 : continue;
1362 159 : if (isl_tab_is_redundant(info->tab, bmap->n_eq + l))
1363 1 : continue;
1364 :
1365 158 : added = add_wrap(wraps, w, bound, bmap->ineq[l], len, set, 0);
1366 158 : if (added < 0)
1367 0 : return isl_stat_error;
1368 158 : if (!added)
1369 111 : goto unbounded;
1370 47 : ++w;
1371 : }
1372 174 : for (l = 0; l < bmap->n_eq; ++l) {
1373 111 : if (isl_seq_is_neg(bound, bmap->eq[l], len))
1374 26 : continue;
1375 85 : if (isl_seq_eq(bound, bmap->eq[l], len))
1376 28 : continue;
1377 :
1378 168 : for (m = 0; m < 2; ++m) {
1379 114 : if (info->eq[2 * l + m] == STATUS_VALID)
1380 80 : continue;
1381 34 : added = add_wrap(wraps, w, bound, bmap->eq[l], len,
1382 : set, !m);
1383 34 : if (added < 0)
1384 0 : return isl_stat_error;
1385 34 : if (!added)
1386 3 : goto unbounded;
1387 31 : ++w;
1388 : }
1389 : }
1390 :
1391 63 : wraps->mat->n_row = w;
1392 63 : return isl_stat_ok;
1393 : unbounded:
1394 114 : 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 50 : static int check_wraps(__isl_keep isl_mat *wraps, int first,
1402 : struct isl_tab *tab)
1403 : {
1404 : int i;
1405 :
1406 100 : for (i = first; i < wraps->n_row; ++i) {
1407 : enum isl_ineq_type type;
1408 2 : type = isl_tab_ineq_type(tab, wraps->row[i]);
1409 2 : if (type == isl_ineq_error)
1410 0 : return -1;
1411 2 : if (type == isl_ineq_redundant)
1412 0 : continue;
1413 2 : wraps->n_row = 0;
1414 2 : return 0;
1415 : }
1416 :
1417 48 : 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 235 : 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 235 : bmap = isl_basic_map_copy(bmap);
1442 235 : bset = isl_basic_map_underlying_set(bmap);
1443 235 : bset = isl_basic_set_cow(bset);
1444 235 : bset = isl_basic_set_update_from_tab(bset, tab);
1445 235 : 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 59 : static isl_bool has_non_validated_redundant_cuts(struct isl_coalesce_info *info)
1455 : {
1456 : int l;
1457 : int n_eq, n_ineq;
1458 59 : int any_redundant_cut = 0;
1459 59 : int any_non_redundant_cut = 0;
1460 :
1461 59 : n_eq = isl_basic_map_n_equality(info->bmap);
1462 59 : n_ineq = isl_basic_map_n_inequality(info->bmap);
1463 59 : if (n_eq < 0 || n_ineq < 0)
1464 0 : return isl_bool_error;
1465 553 : for (l = 0; l < n_ineq; ++l) {
1466 : int red;
1467 :
1468 494 : if (info->ineq[l] != STATUS_CUT)
1469 327 : continue;
1470 167 : red = isl_tab_is_redundant(info->tab, n_eq + l);
1471 167 : if (red < 0)
1472 0 : return isl_bool_error;
1473 167 : if (red)
1474 9 : any_redundant_cut = 1;
1475 : else
1476 158 : any_non_redundant_cut = 1;
1477 : }
1478 59 : if (!any_redundant_cut)
1479 50 : return isl_bool_false;
1480 9 : if (any_non_redundant_cut)
1481 9 : return isl_bool_true;
1482 0 : for (l = 0; l < n_ineq; ++l) {
1483 0 : if (info->ineq[l] == STATUS_CUT)
1484 0 : info->ineq[l] = STATUS_VALID;
1485 : }
1486 :
1487 0 : 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 59 : 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 59 : unsigned total = isl_basic_map_total_dim(info->bmap);
1521 :
1522 59 : snap = isl_tab_snap(info->tab);
1523 :
1524 59 : if (isl_tab_mark_rational(info->tab) < 0)
1525 0 : return isl_stat_error;
1526 59 : if (isl_tab_select_facet(info->tab, info->bmap->n_eq + k) < 0)
1527 0 : return isl_stat_error;
1528 59 : if (isl_tab_detect_redundant(info->tab) < 0)
1529 0 : return isl_stat_error;
1530 59 : nowrap = has_non_validated_redundant_cuts(info);
1531 59 : if (nowrap < 0)
1532 0 : return isl_stat_error;
1533 :
1534 59 : n = wraps->mat->n_row;
1535 59 : if (!nowrap) {
1536 50 : isl_seq_neg(bound, info->bmap->ineq[k], 1 + total);
1537 :
1538 50 : if (add_wraps(wraps, info, bound, set) < 0)
1539 0 : return isl_stat_error;
1540 : }
1541 :
1542 59 : if (isl_tab_rollback(info->tab, snap) < 0)
1543 0 : return isl_stat_error;
1544 59 : if (nowrap)
1545 9 : return wraps_mark_failed(wraps);
1546 50 : if (check_wraps(wraps->mat, n, info->tab) < 0)
1547 0 : return isl_stat_error;
1548 :
1549 50 : 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 108 : 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 108 : enum isl_change change = isl_change_none;
1577 : struct isl_wraps wraps;
1578 : isl_ctx *ctx;
1579 : isl_mat *mat;
1580 108 : struct isl_set *set_i = NULL;
1581 108 : struct isl_set *set_j = NULL;
1582 108 : struct isl_vec *bound = NULL;
1583 108 : unsigned total = isl_basic_map_total_dim(info[i].bmap);
1584 :
1585 108 : set_i = set_from_updated_bmap(info[i].bmap, info[i].tab);
1586 108 : set_j = set_from_updated_bmap(info[j].bmap, info[j].tab);
1587 108 : ctx = isl_basic_map_get_ctx(info[i].bmap);
1588 324 : mat = isl_mat_alloc(ctx, 2 * (info[i].bmap->n_eq + info[j].bmap->n_eq) +
1589 216 : info[i].bmap->n_ineq + info[j].bmap->n_ineq,
1590 : 1 + total);
1591 108 : if (wraps_init(&wraps, mat, info, i, j) < 0)
1592 0 : goto error;
1593 108 : bound = isl_vec_alloc(ctx, 1 + total);
1594 108 : if (!set_i || !set_j || !bound)
1595 : goto error;
1596 :
1597 108 : isl_seq_cpy(bound->el, info[i].bmap->ineq[k], 1 + total);
1598 108 : isl_int_add_ui(bound->el[0], bound->el[0], 1);
1599 108 : isl_seq_normalize(ctx, bound->el, 1 + total);
1600 :
1601 108 : isl_seq_cpy(wraps.mat->row[0], bound->el, 1 + total);
1602 108 : wraps.mat->n_row = 1;
1603 :
1604 108 : if (add_wraps(&wraps, &info[j], bound->el, set_i) < 0)
1605 0 : goto error;
1606 108 : if (!wraps.mat->n_row)
1607 48 : goto unbounded;
1608 :
1609 60 : if (wrap_facet) {
1610 59 : if (add_wraps_around_facet(&wraps, &info[i], k,
1611 : bound->el, set_j) < 0)
1612 0 : goto error;
1613 59 : if (!wraps.mat->n_row)
1614 59 : goto unbounded;
1615 : }
1616 :
1617 1 : change = fuse(i, j, info, wraps.mat, 0, 0);
1618 :
1619 : unbounded:
1620 108 : wraps_free(&wraps);
1621 :
1622 108 : isl_set_free(set_i);
1623 108 : isl_set_free(set_j);
1624 :
1625 108 : isl_vec_free(bound);
1626 :
1627 108 : 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 19 : 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 19 : isl_int_add_ui(wraps->mat->row[w][0], wraps->mat->row[w][0], 1);
1662 19 : if (isl_tab_add_eq(info_j->tab, wraps->mat->row[w]) < 0)
1663 0 : return isl_stat_error;
1664 19 : if (isl_tab_detect_redundant(info_j->tab) < 0)
1665 0 : return isl_stat_error;
1666 :
1667 19 : if (info_j->tab->empty)
1668 0 : isl_int_sub_ui(wraps->mat->row[w][0], wraps->mat->row[w][0], 1);
1669 19 : else if (add_wraps(wraps, info_j, wraps->mat->row[w], set_i) < 0)
1670 0 : return isl_stat_error;
1671 :
1672 19 : if (isl_tab_rollback(info_j->tab, snap) < 0)
1673 0 : return isl_stat_error;
1674 :
1675 19 : 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 19 : 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 19 : total = isl_basic_map_total_dim(info[i].bmap);
1704 :
1705 19 : snap = isl_tab_snap(info[j].tab);
1706 :
1707 19 : wraps->mat->n_row = 0;
1708 :
1709 22 : for (k = 0; k < info[i].bmap->n_eq; ++k) {
1710 9 : for (l = 0; l < 2; ++l) {
1711 6 : if (info[i].eq[2 * k + l] != STATUS_CUT)
1712 6 : continue;
1713 0 : w = wraps->mat->n_row++;
1714 0 : if (l == 0)
1715 0 : isl_seq_neg(wraps->mat->row[w],
1716 0 : info[i].bmap->eq[k], 1 + total);
1717 : else
1718 0 : isl_seq_cpy(wraps->mat->row[w],
1719 0 : info[i].bmap->eq[k], 1 + total);
1720 0 : if (wrap_in_facet(wraps, w, &info[j], set_i, snap) < 0)
1721 0 : return isl_change_error;
1722 :
1723 0 : if (!wraps->mat->n_row)
1724 0 : return isl_change_none;
1725 : }
1726 : }
1727 :
1728 51 : for (k = 0; k < info[i].bmap->n_ineq; ++k) {
1729 50 : if (info[i].ineq[k] != STATUS_CUT)
1730 31 : continue;
1731 19 : w = wraps->mat->n_row++;
1732 38 : isl_seq_cpy(wraps->mat->row[w],
1733 19 : info[i].bmap->ineq[k], 1 + total);
1734 19 : if (wrap_in_facet(wraps, w, &info[j], set_i, snap) < 0)
1735 0 : return isl_change_error;
1736 :
1737 19 : if (!wraps->mat->n_row)
1738 18 : return isl_change_none;
1739 : }
1740 :
1741 1 : 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 19 : static enum isl_change wrap_in_facets(int i, int j, int n,
1756 : struct isl_coalesce_info *info)
1757 : {
1758 19 : enum isl_change change = isl_change_none;
1759 : struct isl_wraps wraps;
1760 : isl_ctx *ctx;
1761 : isl_mat *mat;
1762 19 : isl_set *set_i = NULL;
1763 19 : unsigned total = isl_basic_map_total_dim(info[i].bmap);
1764 : int max_wrap;
1765 :
1766 19 : if (isl_tab_extend_cons(info[j].tab, 1) < 0)
1767 0 : return isl_change_error;
1768 :
1769 19 : max_wrap = 1 + 2 * info[j].bmap->n_eq + info[j].bmap->n_ineq;
1770 19 : max_wrap *= n;
1771 :
1772 19 : set_i = set_from_updated_bmap(info[i].bmap, info[i].tab);
1773 19 : ctx = isl_basic_map_get_ctx(info[i].bmap);
1774 19 : mat = isl_mat_alloc(ctx, max_wrap, 1 + total);
1775 19 : if (wraps_init(&wraps, mat, info, i, j) < 0)
1776 0 : goto error;
1777 19 : if (!set_i)
1778 0 : goto error;
1779 :
1780 19 : change = try_wrap_in_facets(i, j, info, &wraps, set_i);
1781 :
1782 19 : wraps_free(&wraps);
1783 19 : isl_set_free(set_i);
1784 :
1785 19 : 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 2560 : static enum isl_ineq_type type_of_relaxed(struct isl_tab *tab, isl_int *ineq)
1796 : {
1797 : enum isl_ineq_type type;
1798 :
1799 2560 : isl_int_add_ui(ineq[0], ineq[0], 1);
1800 2560 : type = isl_tab_ineq_type(tab, ineq);
1801 2560 : isl_int_sub_ui(ineq[0], ineq[0], 1);
1802 :
1803 2560 : 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 2444 : 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 4888 : if (ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_RATIONAL) ||
1873 2444 : ISL_F_ISSET(info[j].bmap, ISL_BASIC_MAP_RATIONAL))
1874 0 : return isl_change_none;
1875 :
1876 2444 : n = count_eq(&info[i], STATUS_CUT) + count_ineq(&info[i], STATUS_CUT);
1877 2444 : if (n == 0)
1878 0 : return isl_change_none;
1879 :
1880 2444 : total = isl_basic_map_total_dim(info[i].bmap);
1881 2476 : for (k = 0; k < info[i].bmap->n_eq; ++k) {
1882 167 : for (l = 0; l < 2; ++l) {
1883 : enum isl_ineq_type type;
1884 :
1885 135 : if (info[i].eq[2 * k + l] != STATUS_CUT)
1886 77 : continue;
1887 :
1888 58 : if (l == 0)
1889 90 : isl_seq_neg(info[i].bmap->eq[k],
1890 45 : info[i].bmap->eq[k], 1 + total);
1891 58 : type = type_of_relaxed(info[j].tab,
1892 58 : info[i].bmap->eq[k]);
1893 58 : if (l == 0)
1894 90 : isl_seq_neg(info[i].bmap->eq[k],
1895 45 : info[i].bmap->eq[k], 1 + total);
1896 58 : if (type == isl_ineq_error)
1897 0 : return isl_change_error;
1898 58 : if (type != isl_ineq_redundant)
1899 58 : return isl_change_none;
1900 : }
1901 : }
1902 :
1903 5235 : for (k = 0; k < info[i].bmap->n_ineq; ++k) {
1904 : enum isl_ineq_type type;
1905 :
1906 5216 : if (info[i].ineq[k] != STATUS_CUT)
1907 2787 : continue;
1908 :
1909 2429 : type = type_of_relaxed(info[j].tab, info[i].bmap->ineq[k]);
1910 2429 : if (type == isl_ineq_error)
1911 0 : return isl_change_error;
1912 2429 : if (type != isl_ineq_redundant)
1913 2367 : return isl_change_none;
1914 : }
1915 :
1916 19 : 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 1218 : static enum isl_change check_wrap(int i, int j, struct isl_coalesce_info *info)
1924 : {
1925 1218 : enum isl_change change = isl_change_none;
1926 :
1927 1218 : change = can_wrap_in_set(i, j, info);
1928 1218 : if (change != isl_change_none)
1929 0 : return change;
1930 :
1931 1218 : change = can_wrap_in_set(j, i, info);
1932 1218 : 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 73 : 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 73 : n = 0;
1946 192 : for (l = 0; l < info[i].bmap->n_ineq; ++l) {
1947 : enum isl_ineq_type type;
1948 :
1949 188 : if (info[i].ineq[l] != STATUS_CUT)
1950 115 : continue;
1951 73 : type = type_of_relaxed(info[j].tab, info[i].bmap->ineq[l]);
1952 73 : if (type == isl_ineq_error)
1953 0 : return isl_bool_error;
1954 73 : if (type != isl_ineq_redundant)
1955 69 : return isl_bool_false;
1956 4 : list[n++] = l;
1957 : }
1958 :
1959 4 : 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 130 : static enum isl_change check_single_adj_eq(int i, int j,
1979 : struct isl_coalesce_info *info)
1980 : {
1981 130 : 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 130 : n_cut = count_ineq(&info[i], STATUS_CUT);
1989 :
1990 130 : k = find_ineq(&info[i], STATUS_ADJ_EQ);
1991 :
1992 130 : if (n_cut > 0) {
1993 73 : ctx = isl_basic_map_get_ctx(info[i].bmap);
1994 73 : relax = isl_calloc_array(ctx, int, 1 + n_cut);
1995 73 : if (!relax)
1996 0 : return isl_change_error;
1997 73 : relax[0] = k;
1998 73 : try_relax = all_cut_by_one(i, j, info, relax + 1);
1999 73 : if (try_relax < 0)
2000 0 : change = isl_change_error;
2001 : } else {
2002 57 : try_relax = isl_bool_true;
2003 57 : relax = &k;
2004 : }
2005 130 : if (try_relax && change == isl_change_none)
2006 61 : change = is_relaxed_extension(i, j, 1 + n_cut, relax, info);
2007 130 : if (n_cut > 0)
2008 73 : free(relax);
2009 130 : if (change != isl_change_none)
2010 27 : return change;
2011 :
2012 103 : change = can_wrap_in_facet(i, j, k, info, n_cut > 0);
2013 :
2014 103 : 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 316 : static enum isl_change check_adj_eq(int i, int j,
2028 : struct isl_coalesce_info *info)
2029 : {
2030 360 : if (any_eq(&info[i], STATUS_ADJ_INEQ) &&
2031 44 : any_eq(&info[j], STATUS_ADJ_INEQ))
2032 : /* ADJ EQ TOO MANY */
2033 5 : return isl_change_none;
2034 :
2035 311 : if (any_eq(&info[i], STATUS_ADJ_INEQ))
2036 39 : return check_adj_eq(j, i, info);
2037 :
2038 : /* j has an equality adjacent to an inequality in i */
2039 :
2040 272 : if (count_ineq(&info[i], STATUS_ADJ_EQ) != 1) {
2041 77 : if (all_valid_or_cut(&info[i]))
2042 8 : return can_wrap_in_set(i, j, info);
2043 69 : return isl_change_none;
2044 : }
2045 195 : if (any_eq(&info[i], STATUS_CUT))
2046 8 : return isl_change_none;
2047 374 : if (any_ineq(&info[j], STATUS_ADJ_EQ) ||
2048 317 : any_ineq(&info[i], STATUS_ADJ_INEQ) ||
2049 130 : any_ineq(&info[j], STATUS_ADJ_INEQ))
2050 : /* ADJ EQ TOO MANY */
2051 57 : return isl_change_none;
2052 :
2053 130 : 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 47 : static enum isl_change check_ineq_adj_eq(int i, int j,
2069 : struct isl_coalesce_info *info)
2070 : {
2071 : int k;
2072 :
2073 47 : if (any_eq(&info[i], STATUS_CUT))
2074 0 : return isl_change_none;
2075 47 : if (any_ineq(&info[i], STATUS_CUT))
2076 36 : return isl_change_none;
2077 11 : if (any_ineq(&info[i], STATUS_ADJ_INEQ))
2078 6 : return isl_change_none;
2079 5 : if (count_ineq(&info[i], STATUS_ADJ_EQ) != 1)
2080 0 : return isl_change_none;
2081 :
2082 5 : k = find_ineq(&info[i], STATUS_ADJ_EQ);
2083 :
2084 5 : 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 0 : static enum isl_change check_eq_adj_eq(int i, int j,
2106 : struct isl_coalesce_info *info)
2107 : {
2108 : int k;
2109 0 : enum isl_change change = isl_change_none;
2110 0 : int detect_equalities = 0;
2111 : struct isl_wraps wraps;
2112 : isl_ctx *ctx;
2113 : isl_mat *mat;
2114 0 : struct isl_set *set_i = NULL;
2115 0 : struct isl_set *set_j = NULL;
2116 0 : struct isl_vec *bound = NULL;
2117 0 : unsigned total = isl_basic_map_total_dim(info[i].bmap);
2118 :
2119 0 : if (count_eq(&info[i], STATUS_ADJ_EQ) != 1)
2120 0 : detect_equalities = 1;
2121 :
2122 0 : k = find_eq(&info[i], STATUS_ADJ_EQ);
2123 :
2124 0 : set_i = set_from_updated_bmap(info[i].bmap, info[i].tab);
2125 0 : set_j = set_from_updated_bmap(info[j].bmap, info[j].tab);
2126 0 : ctx = isl_basic_map_get_ctx(info[i].bmap);
2127 0 : mat = isl_mat_alloc(ctx, 2 * (info[i].bmap->n_eq + info[j].bmap->n_eq) +
2128 0 : info[i].bmap->n_ineq + info[j].bmap->n_ineq,
2129 : 1 + total);
2130 0 : if (wraps_init(&wraps, mat, info, i, j) < 0)
2131 0 : goto error;
2132 0 : bound = isl_vec_alloc(ctx, 1 + total);
2133 0 : if (!set_i || !set_j || !bound)
2134 : goto error;
2135 :
2136 0 : if (k % 2 == 0)
2137 0 : isl_seq_neg(bound->el, info[i].bmap->eq[k / 2], 1 + total);
2138 : else
2139 0 : isl_seq_cpy(bound->el, info[i].bmap->eq[k / 2], 1 + total);
2140 0 : isl_int_add_ui(bound->el[0], bound->el[0], 1);
2141 :
2142 0 : isl_seq_cpy(wraps.mat->row[0], bound->el, 1 + total);
2143 0 : wraps.mat->n_row = 1;
2144 :
2145 0 : if (add_wraps(&wraps, &info[j], bound->el, set_i) < 0)
2146 0 : goto error;
2147 0 : if (!wraps.mat->n_row)
2148 0 : goto unbounded;
2149 :
2150 0 : isl_int_sub_ui(bound->el[0], bound->el[0], 1);
2151 0 : isl_seq_neg(bound->el, bound->el, 1 + total);
2152 :
2153 0 : isl_seq_cpy(wraps.mat->row[wraps.mat->n_row], bound->el, 1 + total);
2154 0 : wraps.mat->n_row++;
2155 :
2156 0 : if (add_wraps(&wraps, &info[i], bound->el, set_j) < 0)
2157 0 : goto error;
2158 0 : if (!wraps.mat->n_row)
2159 0 : goto unbounded;
2160 :
2161 0 : 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 0 : wraps_free(&wraps);
2169 0 : isl_set_free(set_i);
2170 0 : isl_set_free(set_j);
2171 0 : isl_vec_free(bound);
2172 :
2173 0 : return change;
2174 : }
2175 :
2176 : /* Initialize the "eq" and "ineq" fields of "info".
2177 : */
2178 50360 : static void init_status(struct isl_coalesce_info *info)
2179 : {
2180 50360 : info->eq = info->ineq = NULL;
2181 50360 : }
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 13520 : static void set_eq_status_in(struct isl_coalesce_info *info,
2188 : struct isl_tab *tab)
2189 : {
2190 13520 : if (info->eq)
2191 611 : return;
2192 12909 : 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 31934 : static void set_ineq_status_in(struct isl_coalesce_info *info,
2200 : struct isl_tab *tab)
2201 : {
2202 31934 : if (info->ineq)
2203 744 : return;
2204 31190 : 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 50360 : static void clear_status(struct isl_coalesce_info *info)
2213 : {
2214 50360 : free(info->eq);
2215 50360 : free(info->ineq);
2216 50360 : }
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 57 : static int all_ineq_valid_or_single_adj_ineq(struct isl_coalesce_info *info)
2223 : {
2224 : int i;
2225 57 : int k = -1;
2226 :
2227 152 : for (i = 0; i < info->bmap->n_ineq; ++i) {
2228 151 : if (info->ineq[i] == STATUS_REDUNDANT)
2229 15 : continue;
2230 136 : if (info->ineq[i] == STATUS_VALID)
2231 58 : continue;
2232 78 : if (info->ineq[i] != STATUS_ADJ_INEQ)
2233 54 : return 0;
2234 24 : if (k != -1)
2235 2 : return 0;
2236 22 : k = i;
2237 : }
2238 :
2239 1 : 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 69 : static enum isl_change separating_equality(int i, int j,
2255 : struct isl_coalesce_info *info)
2256 : {
2257 69 : enum isl_change change = isl_change_none;
2258 :
2259 126 : if (all(info[j].eq, 2 * info[j].bmap->n_eq, STATUS_VALID) &&
2260 57 : all_ineq_valid_or_single_adj_ineq(&info[j]))
2261 1 : change = is_adj_ineq_extension(j, i, info);
2262 :
2263 69 : clear_status(&info[i]);
2264 69 : clear_status(&info[j]);
2265 69 : 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 23646 : static enum isl_change coalesce_local_pair_reuse(int i, int j,
2355 : struct isl_coalesce_info *info)
2356 : {
2357 23646 : enum isl_change change = isl_change_none;
2358 :
2359 23646 : set_ineq_status_in(&info[i], info[j].tab);
2360 23646 : if (info[i].bmap->n_ineq && !info[i].ineq)
2361 0 : goto error;
2362 23646 : if (any_ineq(&info[i], STATUS_ERROR))
2363 0 : goto error;
2364 23646 : if (any_ineq(&info[i], STATUS_SEPARATE))
2365 15358 : goto done;
2366 :
2367 8288 : set_ineq_status_in(&info[j], info[i].tab);
2368 8288 : if (info[j].bmap->n_ineq && !info[j].ineq)
2369 0 : goto error;
2370 8288 : if (any_ineq(&info[j], STATUS_ERROR))
2371 0 : goto error;
2372 8288 : if (any_ineq(&info[j], STATUS_SEPARATE))
2373 1528 : goto done;
2374 :
2375 6760 : set_eq_status_in(&info[i], info[j].tab);
2376 6760 : if (info[i].bmap->n_eq && !info[i].eq)
2377 0 : goto error;
2378 6760 : if (any_eq(&info[i], STATUS_ERROR))
2379 0 : goto error;
2380 :
2381 6760 : set_eq_status_in(&info[j], info[i].tab);
2382 6760 : if (info[j].bmap->n_eq && !info[j].eq)
2383 0 : goto error;
2384 6760 : if (any_eq(&info[j], STATUS_ERROR))
2385 0 : goto error;
2386 :
2387 6760 : if (any_eq(&info[i], STATUS_SEPARATE))
2388 9 : return separating_equality(i, j, info);
2389 6751 : if (any_eq(&info[j], STATUS_SEPARATE))
2390 60 : return separating_equality(j, i, info);
2391 :
2392 13262 : if (all(info[i].eq, 2 * info[i].bmap->n_eq, STATUS_VALID) &&
2393 6571 : all(info[i].ineq, info[i].bmap->n_ineq, STATUS_VALID)) {
2394 299 : drop(&info[j]);
2395 299 : change = isl_change_drop_second;
2396 12330 : } else if (all(info[j].eq, 2 * info[j].bmap->n_eq, STATUS_VALID) &&
2397 5938 : all(info[j].ineq, info[j].bmap->n_ineq, STATUS_VALID)) {
2398 129 : drop(&info[i]);
2399 129 : change = isl_change_drop_first;
2400 6263 : } else if (any_eq(&info[i], STATUS_ADJ_EQ)) {
2401 0 : change = check_eq_adj_eq(i, j, info);
2402 6263 : } else if (any_eq(&info[j], STATUS_ADJ_EQ)) {
2403 0 : change = check_eq_adj_eq(j, i, info);
2404 12482 : } else if (any_eq(&info[i], STATUS_ADJ_INEQ) ||
2405 6219 : any_eq(&info[j], STATUS_ADJ_INEQ)) {
2406 277 : change = check_adj_eq(i, j, info);
2407 5986 : } else if (any_ineq(&info[i], STATUS_ADJ_EQ)) {
2408 41 : change = check_ineq_adj_eq(i, j, info);
2409 5945 : } else if (any_ineq(&info[j], STATUS_ADJ_EQ)) {
2410 6 : change = check_ineq_adj_eq(j, i, info);
2411 7169 : } else if (any_ineq(&info[i], STATUS_ADJ_INEQ) ||
2412 1230 : any_ineq(&info[j], STATUS_ADJ_INEQ)) {
2413 4717 : change = check_adj_ineq(i, j, info);
2414 : } else {
2415 2431 : if (!any_eq(&info[i], STATUS_CUT) &&
2416 1209 : !any_eq(&info[j], STATUS_CUT))
2417 1175 : change = check_facets(i, j, info);
2418 1222 : if (change == isl_change_none)
2419 1218 : change = check_wrap(i, j, info);
2420 : }
2421 :
2422 : done:
2423 23577 : clear_status(&info[i]);
2424 23577 : clear_status(&info[j]);
2425 23577 : 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 22902 : static enum isl_change coalesce_local_pair(int i, int j,
2440 : struct isl_coalesce_info *info)
2441 : {
2442 22902 : init_status(&info[i]);
2443 22902 : init_status(&info[j]);
2444 22902 : 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 0 : static isl_stat shift_div(struct isl_coalesce_info *info, int div,
2459 : isl_int shift)
2460 : {
2461 : unsigned total;
2462 :
2463 0 : info->bmap = isl_basic_map_shift_div(info->bmap, div, 0, shift);
2464 0 : if (!info->bmap)
2465 0 : return isl_stat_error;
2466 :
2467 0 : total = isl_basic_map_dim(info->bmap, isl_dim_all);
2468 0 : total -= isl_basic_map_dim(info->bmap, isl_dim_div);
2469 0 : if (isl_tab_shift_var(info->tab, total + div, shift) < 0)
2470 0 : return isl_stat_error;
2471 :
2472 0 : 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 0 : 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 0 : defined = isl_basic_map_has_defining_equality(info->bmap, isl_dim_div,
2512 : div, &c);
2513 0 : if (defined < 0)
2514 0 : return isl_stat_error;
2515 0 : if (!defined)
2516 0 : return isl_stat_ok;
2517 0 : if (!c)
2518 0 : return isl_stat_error;
2519 0 : valid = isl_constraint_is_div_equality(c, div);
2520 0 : isl_int_init(shift);
2521 0 : isl_int_init(stride);
2522 0 : isl_constraint_get_constant(c, &shift);
2523 0 : isl_constraint_get_coefficient(c, isl_dim_div, div, &stride);
2524 0 : isl_int_fdiv_q(shift, shift, stride);
2525 0 : r = shift_div(info, div, shift);
2526 0 : isl_int_clear(stride);
2527 0 : isl_int_clear(shift);
2528 0 : isl_constraint_free(c);
2529 0 : if (r < 0 || valid < 0)
2530 0 : return isl_stat_error;
2531 0 : if (!valid)
2532 0 : return isl_stat_ok;
2533 0 : info->bmap = isl_basic_map_set_div_expr_constant_num_si_inplace(
2534 : info->bmap, div, 0);
2535 0 : if (!info->bmap)
2536 0 : return isl_stat_error;
2537 0 : 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 1370 : static isl_stat harmonize_stride_divs(struct isl_coalesce_info *info1,
2553 : struct isl_coalesce_info *info2)
2554 : {
2555 : int i, n;
2556 :
2557 1370 : n = isl_basic_map_dim(info1->bmap, isl_dim_div);
2558 2740 : for (i = 0; i < n; ++i) {
2559 : isl_bool known, harmonize;
2560 :
2561 1370 : known = isl_basic_map_div_is_known(info1->bmap, i);
2562 1370 : if (known >= 0 && known)
2563 1072 : known = isl_basic_map_div_is_known(info2->bmap, i);
2564 1370 : if (known < 0)
2565 0 : return isl_stat_error;
2566 1370 : if (!known)
2567 370 : continue;
2568 1000 : harmonize = isl_basic_map_equal_div_expr_except_constant(
2569 : info1->bmap, i, info2->bmap, i);
2570 1000 : if (harmonize < 0)
2571 0 : return isl_stat_error;
2572 1000 : if (!harmonize)
2573 1000 : continue;
2574 0 : if (normalize_stride_div(info1, i) < 0)
2575 0 : return isl_stat_error;
2576 0 : if (normalize_stride_div(info2, i) < 0)
2577 0 : return isl_stat_error;
2578 : }
2579 :
2580 1370 : 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 0 : 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 0 : cst = isl_aff_is_cst(shift);
2605 0 : if (cst < 0 || !cst)
2606 0 : return cst < 0 ? isl_stat_error : isl_stat_ok;
2607 :
2608 0 : c = isl_aff_get_constant_val(shift);
2609 0 : cst = isl_val_is_int(c);
2610 0 : if (cst >= 0 && cst)
2611 0 : cst = isl_bool_not(isl_val_is_zero(c));
2612 0 : if (cst < 0 || !cst) {
2613 0 : isl_val_free(c);
2614 0 : return cst < 0 ? isl_stat_error : isl_stat_ok;
2615 : }
2616 :
2617 0 : isl_int_init(d);
2618 0 : r = isl_val_get_num_isl_int(c, &d);
2619 0 : if (r >= 0)
2620 0 : r = shift_div(info, div, d);
2621 0 : isl_int_clear(d);
2622 :
2623 0 : isl_val_free(c);
2624 :
2625 0 : 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 63 : 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 63 : total = isl_basic_map_total_dim(info1->bmap);
2670 63 : ls1 = isl_local_space_wrap(isl_basic_map_get_local_space(info1->bmap));
2671 63 : ls2 = isl_local_space_wrap(isl_basic_map_get_local_space(info2->bmap));
2672 126 : for (i = 0; i < info1->bmap->n_div; ++i) {
2673 : isl_stat r;
2674 : isl_aff *div1, *div2;
2675 :
2676 122 : if (!isl_local_space_div_is_known(ls1, i) ||
2677 59 : !isl_local_space_div_is_known(ls2, i))
2678 8 : continue;
2679 55 : if (isl_int_ne(info1->bmap->div[i][0], info2->bmap->div[i][0]))
2680 0 : continue;
2681 110 : if (isl_seq_eq(info1->bmap->div[i] + 1,
2682 110 : info2->bmap->div[i] + 1, 1 + total))
2683 55 : continue;
2684 0 : div1 = isl_local_space_get_div(ls1, i);
2685 0 : div2 = isl_local_space_get_div(ls2, i);
2686 0 : div1 = isl_aff_substitute_equalities(div1,
2687 : isl_basic_set_copy(eq2));
2688 0 : div2 = isl_aff_substitute_equalities(div2,
2689 : isl_basic_set_copy(eq1));
2690 0 : div2 = isl_aff_sub(div2, div1);
2691 0 : r = shift_if_cst_int(info1, i, div2);
2692 0 : isl_aff_free(div2);
2693 0 : if (r < 0)
2694 0 : break;
2695 : }
2696 63 : isl_local_space_free(ls1);
2697 63 : isl_local_space_free(ls2);
2698 :
2699 63 : if (i < info1->bmap->n_div)
2700 0 : return isl_stat_error;
2701 63 : 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 26419 : 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 26419 : if (!info1->bmap || !info2->bmap)
2736 0 : return isl_stat_error;
2737 :
2738 26419 : if (info1->bmap->n_div != info2->bmap->n_div)
2739 3517 : return isl_stat_ok;
2740 22902 : if (info1->bmap->n_div == 0)
2741 21532 : return isl_stat_ok;
2742 :
2743 1370 : if (harmonize_stride_divs(info1, info2) < 0)
2744 0 : return isl_stat_error;
2745 :
2746 1370 : bmap1 = isl_basic_map_copy(info1->bmap);
2747 1370 : bmap2 = isl_basic_map_copy(info2->bmap);
2748 1370 : eq1 = isl_basic_map_wrap(isl_basic_map_plain_affine_hull(bmap1));
2749 1370 : eq2 = isl_basic_map_wrap(isl_basic_map_plain_affine_hull(bmap2));
2750 1370 : equal = isl_basic_set_plain_is_equal(eq1, eq2);
2751 1370 : if (equal < 0)
2752 0 : r = isl_stat_error;
2753 1370 : else if (equal)
2754 1307 : r = isl_stat_ok;
2755 : else
2756 63 : r = harmonize_divs_with_hulls(info1, info2, eq1, eq2);
2757 1370 : isl_basic_set_free(eq1);
2758 1370 : isl_basic_set_free(eq2);
2759 :
2760 1370 : 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 26419 : 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 26419 : if (!bmap1 || !bmap2)
2776 0 : return isl_bool_error;
2777 26419 : if (bmap1->n_div != bmap2->n_div)
2778 3517 : return isl_bool_false;
2779 :
2780 22902 : if (bmap1->n_div == 0)
2781 21532 : return isl_bool_true;
2782 :
2783 1370 : known = isl_basic_map_divs_known(bmap1);
2784 1370 : if (known < 0 || !known)
2785 298 : return known;
2786 1072 : known = isl_basic_map_divs_known(bmap2);
2787 1072 : if (known < 0 || !known)
2788 72 : return known;
2789 :
2790 1000 : total = isl_basic_map_total_dim(bmap1);
2791 2000 : for (i = 0; i < bmap1->n_div; ++i)
2792 1000 : if (!isl_seq_eq(bmap1->div[i], bmap2->div[i], 2 + total))
2793 0 : return isl_bool_false;
2794 :
2795 1000 : 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 744 : static isl_stat copy_ineq(struct isl_tab *tab, __isl_keep isl_basic_map *bmap)
2803 : {
2804 : int i, n_ineq;
2805 :
2806 744 : if (!bmap)
2807 0 : return isl_stat_error;
2808 :
2809 744 : n_ineq = tab->n_con - tab->n_eq;
2810 2232 : for (i = n_ineq; i < bmap->n_ineq; ++i)
2811 1488 : if (isl_tab_add_ineq(tab, bmap->ineq[i]) < 0)
2812 0 : return isl_stat_error;
2813 :
2814 744 : 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 0 : 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 0 : o_div = isl_basic_map_offset(info->bmap, isl_dim_div) - 1;
2864 0 : ineq = isl_vec_alloc(isl_tab_get_ctx(info->tab), 1 + info->tab->n_var);
2865 0 : if (!ineq)
2866 0 : return isl_stat_error;
2867 0 : isl_seq_clr(ineq->el + 1, info->tab->n_var);
2868 :
2869 0 : for (i = 0; i < n; ++i) {
2870 0 : if (!expanded[i].cst) {
2871 0 : info->bmap = isl_basic_map_extend_constraints(
2872 : info->bmap, 0, 2);
2873 0 : if (isl_basic_map_add_div_constraints(info->bmap,
2874 0 : expanded[i].pos - o_div) < 0)
2875 0 : break;
2876 : } else {
2877 0 : isl_int_set_si(ineq->el[1 + expanded[i].pos], -1);
2878 0 : isl_int_set(ineq->el[0], expanded[i].val);
2879 0 : info->bmap = isl_basic_map_add_ineq(info->bmap,
2880 : ineq->el);
2881 0 : isl_int_set_si(ineq->el[1 + expanded[i].pos], 1);
2882 0 : isl_int_neg(ineq->el[0], expanded[i].val);
2883 0 : info->bmap = isl_basic_map_add_ineq(info->bmap,
2884 : ineq->el);
2885 0 : isl_int_set_si(ineq->el[1 + expanded[i].pos], 0);
2886 : }
2887 0 : if (copy_ineq(info->tab, info->bmap) < 0)
2888 0 : break;
2889 0 : if (expanded[i].cst &&
2890 0 : isl_tab_select_facet(info->tab, info->tab->n_con - 1) < 0)
2891 0 : break;
2892 : }
2893 :
2894 0 : isl_vec_free(ineq);
2895 :
2896 0 : clear_status(info);
2897 0 : init_status(info);
2898 :
2899 0 : 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 744 : 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 744 : if (!bmap)
2941 0 : return isl_stat_error;
2942 744 : 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 744 : if (isl_tab_extend_vars(info->tab, n) < 0)
2948 0 : goto error;
2949 744 : if (isl_tab_extend_cons(info->tab, 2 * n) < 0)
2950 0 : goto error;
2951 :
2952 1488 : for (i = 0; i < n; ++i) {
2953 744 : if (isl_tab_insert_var(info->tab, expanded[i].pos) < 0)
2954 0 : goto error;
2955 : }
2956 :
2957 744 : snap = isl_tab_snap(info->tab);
2958 :
2959 744 : n_ineq = info->tab->n_con - info->tab->n_eq;
2960 744 : if (copy_ineq(info->tab, bmap) < 0)
2961 0 : goto error;
2962 :
2963 744 : isl_basic_map_free(info->bmap);
2964 744 : info->bmap = bmap;
2965 :
2966 744 : any = 0;
2967 1488 : for (i = 0; i < n; ++i) {
2968 2232 : expanded[i].cst = isl_tab_is_constant(info->tab,
2969 1488 : expanded[i].pos, &expanded[i].val);
2970 744 : if (expanded[i].cst < 0)
2971 0 : return isl_stat_error;
2972 744 : if (expanded[i].cst)
2973 0 : any = 1;
2974 : }
2975 :
2976 744 : if (any) {
2977 0 : if (isl_tab_rollback(info->tab, snap) < 0)
2978 0 : return isl_stat_error;
2979 0 : info->bmap = isl_basic_map_cow(info->bmap);
2980 0 : if (isl_basic_map_free_inequality(info->bmap, 2 * n) < 0)
2981 0 : return isl_stat_error;
2982 :
2983 0 : return fix_constant_divs(info, n, expanded);
2984 : }
2985 :
2986 744 : n_eq = info->bmap->n_eq;
2987 6790 : for (i = 0; i < n_ineq; ++i) {
2988 6046 : if (isl_tab_is_redundant(info->tab, n_eq + i))
2989 1102 : info->ineq[i] = STATUS_REDUNDANT;
2990 : }
2991 :
2992 744 : 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 744 : 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 744 : total = isl_basic_map_dim(bmap, isl_dim_all);
3022 744 : n_div = isl_basic_map_dim(bmap, isl_dim_div);
3023 744 : pos = total - n_div;
3024 744 : extra_var = total - info->tab->n_var;
3025 744 : n = n_div - extra_var;
3026 :
3027 744 : ctx = isl_basic_map_get_ctx(bmap);
3028 744 : expanded = isl_calloc_array(ctx, struct isl_expanded, extra_var);
3029 744 : if (extra_var && !expanded)
3030 0 : goto error;
3031 :
3032 744 : i = 0;
3033 744 : k = 0;
3034 1488 : for (j = 0; j < n_div; ++j) {
3035 744 : if (i < n && exp[i] == j) {
3036 0 : ++i;
3037 0 : continue;
3038 : }
3039 744 : expanded[k++].pos = pos + j;
3040 : }
3041 :
3042 1488 : for (k = 0; k < extra_var; ++k)
3043 744 : isl_int_init(expanded[k].val);
3044 :
3045 744 : r = tab_insert_divs(info, extra_var, expanded, bmap);
3046 :
3047 1488 : for (k = 0; k < extra_var; ++k)
3048 744 : isl_int_clear(expanded[k].val);
3049 744 : free(expanded);
3050 :
3051 744 : 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 1020 : 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 1020 : enum isl_change change = isl_change_none;
3095 :
3096 1020 : known = isl_basic_map_divs_known(info[j].bmap);
3097 1020 : if (known < 0 || !known) {
3098 276 : clear_status(&info[i]);
3099 276 : isl_basic_map_free(bmap);
3100 276 : return known < 0 ? isl_change_error : isl_change_none;
3101 : }
3102 :
3103 744 : bmap_i = isl_basic_map_copy(info[i].bmap);
3104 744 : snap = isl_tab_snap(info[i].tab);
3105 744 : if (expand_tab(&info[i], exp, bmap) < 0)
3106 0 : change = isl_change_error;
3107 :
3108 744 : init_status(&info[j]);
3109 744 : if (change == isl_change_none)
3110 744 : change = coalesce_local_pair_reuse(i, j, info);
3111 : else
3112 0 : clear_status(&info[i]);
3113 744 : if (change != isl_change_none && change != isl_change_drop_second) {
3114 0 : isl_basic_map_free(bmap_i);
3115 : } else {
3116 744 : isl_basic_map_free(info[i].bmap);
3117 744 : info[i].bmap = bmap_i;
3118 :
3119 744 : if (isl_tab_rollback(info[i].tab, snap) < 0)
3120 0 : change = isl_change_error;
3121 : }
3122 :
3123 744 : 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 3812 : 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 3812 : enum isl_change change = isl_change_none;
3155 : struct isl_coalesce_info info_local, *info_i;
3156 :
3157 3812 : info_i = i >= 0 ? &info[i] : &info_local;
3158 3812 : init_status(info_i);
3159 3812 : bmap = isl_basic_map_copy(bmap);
3160 3812 : bmap = isl_basic_map_expand_divs(bmap, isl_mat_copy(div), exp);
3161 3812 : bmap = isl_basic_map_mark_final(bmap);
3162 :
3163 3812 : if (!bmap)
3164 0 : goto error;
3165 :
3166 3812 : info_local.bmap = bmap;
3167 3812 : info_i->eq = eq_status_in(bmap, info[j].tab);
3168 3812 : if (bmap->n_eq && !info_i->eq)
3169 0 : goto error;
3170 3812 : if (any_eq(info_i, STATUS_ERROR))
3171 0 : goto error;
3172 3812 : if (any_eq(info_i, STATUS_SEPARATE))
3173 144 : goto done;
3174 :
3175 3668 : info_i->ineq = ineq_status_in(bmap, NULL, info[j].tab);
3176 3668 : if (bmap->n_ineq && !info_i->ineq)
3177 0 : goto error;
3178 3668 : if (any_ineq(info_i, STATUS_ERROR))
3179 0 : goto error;
3180 3668 : if (any_ineq(info_i, STATUS_SEPARATE))
3181 2360 : goto done;
3182 :
3183 2256 : if (all(info_i->eq, 2 * bmap->n_eq, STATUS_VALID) &&
3184 948 : all(info_i->ineq, bmap->n_ineq, STATUS_VALID)) {
3185 4 : drop(&info[j]);
3186 4 : change = isl_change_drop_second;
3187 : }
3188 :
3189 1308 : if (change == isl_change_none && i != -1)
3190 1020 : return coalesce_expand_tab_divs(bmap, i, j, info, div, exp);
3191 :
3192 : done:
3193 2792 : isl_basic_map_free(bmap);
3194 2792 : clear_status(info_i);
3195 2792 : 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 3815 : 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 3815 : int *exp1 = NULL;
3227 3815 : int *exp2 = NULL;
3228 : isl_ctx *ctx;
3229 : enum isl_change change;
3230 :
3231 3815 : known = isl_basic_map_divs_known(bmap_i);
3232 3815 : if (known < 0)
3233 0 : return isl_change_error;
3234 3815 : if (!known)
3235 3 : return isl_change_none;
3236 :
3237 3812 : ctx = isl_basic_map_get_ctx(bmap_i);
3238 :
3239 3812 : div_i = isl_basic_map_get_divs(bmap_i);
3240 3812 : div_j = isl_basic_map_get_divs(info[j].bmap);
3241 :
3242 3812 : if (!div_i || !div_j)
3243 : goto error;
3244 :
3245 3812 : exp1 = isl_alloc_array(ctx, int, div_i->n_row);
3246 3812 : exp2 = isl_alloc_array(ctx, int, div_j->n_row);
3247 3812 : if ((div_i->n_row && !exp1) || (div_j->n_row && !exp2))
3248 : goto error;
3249 :
3250 3812 : div = isl_merge_divs(div_i, div_j, exp1, exp2);
3251 3812 : if (!div)
3252 0 : goto error;
3253 :
3254 3812 : if (div->n_row == div_j->n_row)
3255 3812 : change = coalesce_with_expanded_divs(bmap_i,
3256 : i, j, info, div, exp1);
3257 : else
3258 0 : change = isl_change_none;
3259 :
3260 3812 : isl_mat_free(div);
3261 :
3262 3812 : isl_mat_free(div_i);
3263 3812 : isl_mat_free(div_j);
3264 :
3265 3812 : free(exp2);
3266 3812 : free(exp1);
3267 :
3268 3812 : 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 7734 : 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 7734 : if (info[j].bmap->n_eq == 0)
3302 7210 : return isl_change_none;
3303 524 : if (info[i].bmap->n_div == 0)
3304 85 : return isl_change_none;
3305 :
3306 439 : hull_i = isl_basic_map_copy(info[i].bmap);
3307 439 : hull_i = isl_basic_map_plain_affine_hull(hull_i);
3308 439 : hull_j = isl_basic_map_copy(info[j].bmap);
3309 439 : hull_j = isl_basic_map_plain_affine_hull(hull_j);
3310 :
3311 439 : hull_j = isl_basic_map_intersect(hull_j, isl_basic_map_copy(hull_i));
3312 439 : equal = isl_basic_map_plain_is_equal(hull_i, hull_j);
3313 439 : empty = isl_basic_map_plain_is_empty(hull_j);
3314 439 : isl_basic_map_free(hull_i);
3315 :
3316 439 : if (equal < 0 || equal || empty < 0 || empty) {
3317 20 : isl_basic_map_free(hull_j);
3318 20 : if (equal < 0 || empty < 0)
3319 0 : return isl_change_error;
3320 20 : return isl_change_none;
3321 : }
3322 :
3323 419 : bmap_i = isl_basic_map_copy(info[i].bmap);
3324 419 : bmap_i = isl_basic_map_intersect(bmap_i, hull_j);
3325 419 : if (!bmap_i)
3326 0 : return isl_change_error;
3327 :
3328 419 : if (bmap_i->n_div > info[j].bmap->n_div) {
3329 121 : isl_basic_map_free(bmap_i);
3330 121 : return isl_change_none;
3331 : }
3332 :
3333 298 : change = coalesce_after_aligning_divs(bmap_i, -1, j, info);
3334 :
3335 298 : isl_basic_map_free(bmap_i);
3336 :
3337 298 : 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 3871 : static enum isl_change coalesce_divs(int i, int j,
3356 : struct isl_coalesce_info *info)
3357 : {
3358 3871 : enum isl_change change = isl_change_none;
3359 :
3360 3871 : if (info[i].bmap->n_div < info[j].bmap->n_div)
3361 2482 : change = coalesce_after_aligning_divs(info[i].bmap, i, j, info);
3362 3871 : if (change != isl_change_none)
3363 4 : return change;
3364 :
3365 3867 : if (info[j].bmap->n_div < info[i].bmap->n_div)
3366 1035 : change = coalesce_after_aligning_divs(info[j].bmap, j, i, info);
3367 3867 : if (change != isl_change_none)
3368 0 : return invert_change(change);
3369 :
3370 3867 : change = coalesce_subset_with_equalities(i, j, info);
3371 3867 : if (change != isl_change_none)
3372 0 : return change;
3373 :
3374 3867 : change = coalesce_subset_with_equalities(j, i, info);
3375 3867 : if (change != isl_change_none)
3376 0 : return invert_change(change);
3377 :
3378 3867 : return isl_change_none;
3379 : }
3380 :
3381 : /* Does "bmap" involve any divs that themselves refer to divs?
3382 : */
3383 4374 : 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 4374 : total = isl_basic_map_dim(bmap, isl_dim_all);
3390 4374 : n_div = isl_basic_map_dim(bmap, isl_dim_div);
3391 4374 : total -= n_div;
3392 :
3393 6561 : for (i = 0; i < n_div; ++i)
3394 2187 : if (isl_seq_first_non_zero(bmap->div[i] + 2 + total,
3395 : n_div) != -1)
3396 0 : return isl_bool_true;
3397 :
3398 4374 : 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 293 : 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 293 : if (!hull)
3425 0 : return NULL;
3426 :
3427 293 : ctx = isl_basic_map_get_ctx(hull);
3428 :
3429 293 : n_div_i = isl_basic_map_dim(bmap_i, isl_dim_div);
3430 293 : n_div_j = isl_basic_map_dim(bmap_j, isl_dim_div);
3431 293 : total = isl_basic_map_total_dim(bmap_i) - n_div_i;
3432 :
3433 293 : ls = isl_basic_map_get_local_space(bmap_i);
3434 293 : ls = isl_local_space_wrap(ls);
3435 293 : wrap_hull = isl_basic_map_wrap(hull);
3436 :
3437 293 : aff_nan = isl_aff_nan_on_domain(isl_local_space_copy(ls));
3438 293 : list = isl_aff_list_alloc(ctx, n_div_i);
3439 :
3440 293 : j = 0;
3441 293 : for (i = 0; i < n_div_i; ++i) {
3442 : isl_aff *aff;
3443 :
3444 293 : if (j < n_div_j &&
3445 0 : isl_basic_map_equal_div_expr_part(bmap_i, i, bmap_j, j,
3446 : 0, 2 + total)) {
3447 0 : ++j;
3448 0 : list = isl_aff_list_add(list, isl_aff_copy(aff_nan));
3449 0 : continue;
3450 : }
3451 293 : if (n_div_i - i <= n_div_j - j)
3452 0 : break;
3453 :
3454 293 : aff = isl_local_space_get_div(ls, i);
3455 293 : aff = isl_aff_substitute_equalities(aff,
3456 : isl_basic_set_copy(wrap_hull));
3457 293 : aff = isl_aff_floor(aff);
3458 293 : if (!aff)
3459 0 : goto error;
3460 293 : if (isl_aff_dim(aff, isl_dim_div) != 0) {
3461 293 : isl_aff_free(aff);
3462 293 : break;
3463 : }
3464 :
3465 0 : list = isl_aff_list_add(list, aff);
3466 : }
3467 :
3468 293 : isl_aff_free(aff_nan);
3469 293 : isl_local_space_free(ls);
3470 293 : isl_basic_set_free(wrap_hull);
3471 :
3472 293 : 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 0 : 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 0 : space = isl_basic_map_get_space(info->bmap);
3504 0 : info->bmap = isl_basic_map_cow(info->bmap);
3505 0 : info->bmap = isl_basic_map_extend_space(info->bmap, space,
3506 : extra_var, 0, 0);
3507 0 : if (!info->bmap)
3508 0 : return isl_stat_error;
3509 0 : n = isl_aff_list_n_aff(list);
3510 0 : for (i = 0; i < n; ++i) {
3511 : int is_nan;
3512 : isl_aff *aff;
3513 :
3514 0 : aff = isl_aff_list_get_aff(list, i);
3515 0 : is_nan = isl_aff_is_nan(aff);
3516 0 : isl_aff_free(aff);
3517 0 : if (is_nan < 0)
3518 0 : return isl_stat_error;
3519 0 : if (is_nan)
3520 0 : continue;
3521 :
3522 0 : if (isl_tab_insert_var(info->tab, dim + i) < 0)
3523 0 : return isl_stat_error;
3524 0 : d = isl_basic_map_alloc_div(info->bmap);
3525 0 : if (d < 0)
3526 0 : return isl_stat_error;
3527 0 : info->bmap = isl_basic_map_mark_div_unknown(info->bmap, d);
3528 0 : if (!info->bmap)
3529 0 : return isl_stat_error;
3530 0 : for (j = d; j > i; --j)
3531 0 : isl_basic_map_swap_div(info->bmap, j - 1, j);
3532 : }
3533 :
3534 0 : 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 0 : 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 0 : n = isl_aff_list_n_aff(list);
3554 :
3555 0 : ctx = isl_tab_get_ctx(tab);
3556 0 : sub = isl_vec_alloc(ctx, 1 + dim + n);
3557 0 : if (!sub)
3558 0 : return -1;
3559 0 : isl_seq_clr(sub->el + 1 + dim, n);
3560 :
3561 0 : for (i = 0; i < n; ++i) {
3562 0 : aff = isl_aff_list_get_aff(list, i);
3563 0 : if (!aff)
3564 0 : goto error;
3565 0 : if (isl_aff_is_nan(aff)) {
3566 0 : isl_aff_free(aff);
3567 0 : continue;
3568 : }
3569 0 : isl_seq_cpy(sub->el, aff->v->el + 1, 1 + dim);
3570 0 : isl_int_neg(sub->el[1 + dim + i], aff->v->el[0]);
3571 0 : if (isl_tab_add_eq(tab, sub->el) < 0)
3572 0 : goto error;
3573 0 : isl_int_set_si(sub->el[1 + dim + i], 0);
3574 0 : isl_aff_free(aff);
3575 : }
3576 :
3577 0 : isl_vec_free(sub);
3578 0 : 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 0 : 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 0 : if (!list)
3600 0 : return -1;
3601 :
3602 0 : n = isl_aff_list_n_aff(list);
3603 0 : extra_var = n - (info->tab->n_var - dim);
3604 :
3605 0 : if (isl_tab_extend_vars(info->tab, extra_var) < 0)
3606 0 : return -1;
3607 0 : if (isl_tab_extend_cons(info->tab, 2 * extra_var) < 0)
3608 0 : return -1;
3609 0 : if (add_sub_vars(info, list, dim, extra_var) < 0)
3610 0 : return -1;
3611 :
3612 0 : 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 0 : 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 0 : bmap_j = isl_basic_map_copy(info[j].bmap);
3637 0 : snap = isl_tab_snap(info[j].tab);
3638 :
3639 0 : dim = isl_basic_map_dim(bmap_j, isl_dim_all);
3640 0 : dim -= isl_basic_map_dim(bmap_j, isl_dim_div);
3641 0 : if (add_subs(&info[j], list, dim) < 0)
3642 0 : goto error;
3643 :
3644 0 : change = coalesce_local_pair(i, j, info);
3645 0 : if (change != isl_change_none && change != isl_change_drop_first) {
3646 0 : isl_basic_map_free(bmap_j);
3647 : } else {
3648 0 : isl_basic_map_free(info[j].bmap);
3649 0 : info[j].bmap = bmap_j;
3650 :
3651 0 : if (isl_tab_rollback(info[j].tab, snap) < 0)
3652 0 : return isl_change_error;
3653 : }
3654 :
3655 0 : 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 4374 : 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 4374 : n_div_i = isl_basic_map_dim(info[i].bmap, isl_dim_div);
3685 4374 : n_div_j = isl_basic_map_dim(info[j].bmap, isl_dim_div);
3686 4374 : if (n_div_i <= n_div_j)
3687 2187 : return isl_change_none;
3688 2187 : if (info[j].bmap->n_eq == 0)
3689 1874 : return isl_change_none;
3690 :
3691 313 : hull_i = isl_basic_map_copy(info[i].bmap);
3692 313 : hull_i = isl_basic_map_plain_affine_hull(hull_i);
3693 313 : hull_j = isl_basic_map_copy(info[j].bmap);
3694 313 : hull_j = isl_basic_map_plain_affine_hull(hull_j);
3695 :
3696 313 : hull_j = isl_basic_map_intersect(hull_j, isl_basic_map_copy(hull_i));
3697 313 : equal = isl_basic_map_plain_is_equal(hull_i, hull_j);
3698 313 : empty = isl_basic_map_plain_is_empty(hull_j);
3699 313 : isl_basic_map_free(hull_i);
3700 :
3701 313 : if (equal < 0 || empty < 0)
3702 : goto error;
3703 313 : if (equal || empty) {
3704 20 : isl_basic_map_free(hull_j);
3705 20 : return isl_change_none;
3706 : }
3707 :
3708 293 : list = set_up_substitutions(info[i].bmap, info[j].bmap, hull_j);
3709 293 : if (!list)
3710 0 : return isl_change_error;
3711 293 : if (isl_aff_list_n_aff(list) < n_div_i)
3712 293 : change = isl_change_none;
3713 : else
3714 0 : change = coalesce_with_subs(i, j, info, list);
3715 :
3716 293 : isl_aff_list_free(list);
3717 :
3718 293 : 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 3867 : 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 3867 : known = isl_basic_map_divs_known(info[i].bmap);
3738 3867 : if (known < 0 || !known)
3739 886 : return known < 0 ? isl_change_error : isl_change_none;
3740 2981 : known = isl_basic_map_divs_known(info[j].bmap);
3741 2981 : if (known < 0 || !known)
3742 794 : return known < 0 ? isl_change_error : isl_change_none;
3743 2187 : nested = has_nested_div(info[i].bmap);
3744 2187 : if (nested < 0 || nested)
3745 0 : return nested < 0 ? isl_change_error : isl_change_none;
3746 2187 : nested = has_nested_div(info[j].bmap);
3747 2187 : if (nested < 0 || nested)
3748 0 : return nested < 0 ? isl_change_error : isl_change_none;
3749 :
3750 2187 : change = check_coalesce_into_eq(i, j, info);
3751 2187 : if (change != isl_change_none)
3752 0 : return change;
3753 2187 : change = check_coalesce_into_eq(j, i, info);
3754 2187 : if (change != isl_change_none)
3755 0 : return invert_change(change);
3756 :
3757 2187 : 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 26419 : 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 26419 : if (harmonize_divs(&info[i], &info[j]) < 0)
3789 0 : return isl_change_error;
3790 26419 : same = same_divs(info[i].bmap, info[j].bmap);
3791 26419 : if (same < 0)
3792 0 : return isl_change_error;
3793 26419 : if (same)
3794 22532 : return coalesce_local_pair(i, j, info);
3795 :
3796 3887 : ctx = isl_basic_map_get_ctx(info[i].bmap);
3797 3887 : preserve = isl_options_get_coalesce_preserve_locals(ctx);
3798 3887 : if (!preserve && info[i].bmap->n_div == info[j].bmap->n_div) {
3799 370 : change = coalesce_local_pair(i, j, info);
3800 370 : if (change != isl_change_none)
3801 16 : return change;
3802 : }
3803 :
3804 3871 : change = coalesce_divs(i, j, info);
3805 3871 : if (change != isl_change_none)
3806 4 : return change;
3807 :
3808 3867 : return check_coalesce_eq(i, j, info);
3809 : }
3810 :
3811 : /* Return the maximum of "a" and "b".
3812 : */
3813 2079 : static int isl_max(int a, int b)
3814 : {
3815 2079 : 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 230 : 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 3390 : for (i = end1 - 1; i >= start1; --i) {
3838 3160 : if (info[i].removed)
3839 1081 : continue;
3840 72046 : for (j = isl_max(i + 1, start2); j < end2; ++j) {
3841 : enum isl_change changed;
3842 :
3843 69967 : if (info[j].removed)
3844 43548 : continue;
3845 26419 : if (info[i].removed)
3846 0 : isl_die(ctx, isl_error_internal,
3847 : "basic map unexpectedly removed",
3848 : return -1);
3849 26419 : changed = coalesce_pair(i, j, info);
3850 26419 : switch (changed) {
3851 : case isl_change_error:
3852 0 : return -1;
3853 : case isl_change_none:
3854 : case isl_change_drop_second:
3855 25488 : continue;
3856 : case isl_change_drop_first:
3857 129 : j = end2;
3858 129 : break;
3859 : case isl_change_fuse:
3860 802 : j = i;
3861 802 : break;
3862 : }
3863 : }
3864 : }
3865 :
3866 230 : 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 38 : static int coalesce(isl_ctx *ctx, int n, struct isl_coalesce_info *info)
3878 : {
3879 : int start, end;
3880 :
3881 153 : for (end = n; end > 0; end = start) {
3882 115 : start = end - 1;
3883 3237 : while (start >= 1 &&
3884 1542 : info[start - 1].hull_hash == info[start].hull_hash)
3885 1465 : start--;
3886 115 : if (coalesce_range(ctx, info, start, end, start, end) < 0)
3887 0 : return -1;
3888 115 : if (coalesce_range(ctx, info, start, end, end, n) < 0)
3889 0 : return -1;
3890 : }
3891 :
3892 38 : 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 38 : 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 38 : if (!map)
3913 0 : return NULL;
3914 :
3915 1618 : for (i = n - 1; i >= 0; --i) {
3916 1580 : if (info[i].removed) {
3917 1234 : isl_basic_map_free(map->p[i]);
3918 1234 : if (i != map->n - 1)
3919 498 : map->p[i] = map->p[map->n - 1];
3920 1234 : map->n--;
3921 1234 : continue;
3922 : }
3923 :
3924 692 : info[i].bmap = isl_basic_map_update_from_tab(info[i].bmap,
3925 346 : info[i].tab);
3926 346 : info[i].bmap = isl_basic_map_gauss(info[i].bmap, NULL);
3927 346 : if (info[i].simplify)
3928 0 : info[i].bmap = isl_basic_map_simplify(info[i].bmap);
3929 346 : info[i].bmap = isl_basic_map_finalize(info[i].bmap);
3930 346 : if (!info[i].bmap)
3931 0 : return isl_map_free(map);
3932 346 : if (!info[i].modified) {
3933 196 : ISL_F_SET(info[i].bmap, ISL_BASIC_MAP_NO_IMPLICIT);
3934 196 : ISL_F_SET(info[i].bmap, ISL_BASIC_MAP_NO_REDUNDANT);
3935 : }
3936 346 : isl_basic_map_free(map->p[i]);
3937 346 : map->p[i] = info[i].bmap;
3938 346 : info[i].bmap = NULL;
3939 : }
3940 :
3941 38 : 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 60 : __isl_give isl_map *isl_map_coalesce(__isl_take isl_map *map)
3970 : {
3971 : int i;
3972 : unsigned n;
3973 : isl_ctx *ctx;
3974 60 : struct isl_coalesce_info *info = NULL;
3975 :
3976 60 : map = isl_map_remove_empty_parts(map);
3977 60 : if (!map)
3978 0 : return NULL;
3979 :
3980 60 : if (map->n <= 1)
3981 22 : return map;
3982 :
3983 38 : ctx = isl_map_get_ctx(map);
3984 38 : map = isl_map_sort_divs(map);
3985 38 : map = isl_map_cow(map);
3986 :
3987 38 : if (!map)
3988 0 : return NULL;
3989 :
3990 38 : n = map->n;
3991 :
3992 38 : info = isl_calloc_array(map->ctx, struct isl_coalesce_info, n);
3993 38 : if (!info)
3994 0 : goto error;
3995 :
3996 1618 : for (i = 0; i < map->n; ++i) {
3997 1580 : map->p[i] = isl_basic_map_reduce_coefficients(map->p[i]);
3998 1580 : if (!map->p[i])
3999 0 : goto error;
4000 1580 : info[i].bmap = isl_basic_map_copy(map->p[i]);
4001 1580 : info[i].tab = isl_tab_from_basic_map(info[i].bmap, 0);
4002 1580 : if (!info[i].tab)
4003 0 : goto error;
4004 1580 : if (!ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_NO_IMPLICIT))
4005 359 : if (isl_tab_detect_implicit_equalities(info[i].tab) < 0)
4006 0 : goto error;
4007 3160 : info[i].bmap = isl_tab_make_equalities_explicit(info[i].tab,
4008 1580 : info[i].bmap);
4009 1580 : if (!info[i].bmap)
4010 0 : goto error;
4011 1580 : if (!ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_NO_REDUNDANT))
4012 368 : if (isl_tab_detect_redundant(info[i].tab) < 0)
4013 0 : goto error;
4014 1580 : if (coalesce_info_set_hull_hash(&info[i]) < 0)
4015 0 : goto error;
4016 : }
4017 1618 : for (i = map->n - 1; i >= 0; --i)
4018 1580 : if (info[i].tab->empty)
4019 0 : drop(&info[i]);
4020 :
4021 38 : if (coalesce(ctx, n, info) < 0)
4022 0 : goto error;
4023 :
4024 38 : map = update_basic_maps(map, n, info);
4025 :
4026 38 : clear_coalesce_info(n, info);
4027 :
4028 38 : 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 60 : struct isl_set *isl_set_coalesce(struct isl_set *set)
4040 : {
4041 60 : return set_from_map(isl_map_coalesce(set_to_map(set)));
4042 : }
|
