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 18671886564 : static int status_in(isl_int *ineq, struct isl_tab *tab)
46 : {
47 18671886564 : enum isl_ineq_type type = isl_tab_ineq_type(tab, ineq);
48 18671886564 : switch (type) {
49 : default:
50 0 : case isl_ineq_error: return STATUS_ERROR;
51 11454554549 : case isl_ineq_redundant: return STATUS_VALID;
52 7173129744 : case isl_ineq_separate: return STATUS_SEPARATE;
53 36518034 : case isl_ineq_cut: return STATUS_CUT;
54 1964249 : case isl_ineq_adj_eq: return STATUS_ADJ_EQ;
55 5719988 : 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 4651740886 : static int *eq_status_in(__isl_keep isl_basic_map *bmap_i,
66 : struct isl_tab *tab_j)
67 : {
68 : int k, l;
69 4651740886 : int *eq = isl_calloc_array(bmap_i->ctx, int, 2 * bmap_i->n_eq);
70 : unsigned dim;
71 :
72 4651740886 : if (!eq)
73 0 : return NULL;
74 :
75 4651740886 : dim = isl_basic_map_total_dim(bmap_i);
76 13940164343 : for (k = 0; k < bmap_i->n_eq; ++k) {
77 27865270371 : for (l = 0; l < 2; ++l) {
78 18576846914 : isl_seq_neg(bmap_i->eq[k], bmap_i->eq[k], 1+dim);
79 18576846914 : eq[2 * k + l] = status_in(bmap_i->eq[k], tab_j);
80 18576846914 : if (eq[2 * k + l] == STATUS_ERROR)
81 0 : goto error;
82 : }
83 : }
84 :
85 4651740886 : 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 4668350509 : 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 4668350509 : unsigned n_eq = bmap_i->n_eq;
100 4668350509 : int *ineq = isl_calloc_array(bmap_i->ctx, int, bmap_i->n_ineq);
101 :
102 4668350509 : if (!ineq)
103 0 : return NULL;
104 :
105 4759569936 : for (k = 0; k < bmap_i->n_ineq; ++k) {
106 102823919 : if (tab_i && isl_tab_is_redundant(tab_i, n_eq + k)) {
107 13614133 : ineq[k] = STATUS_REDUNDANT;
108 13614133 : continue;
109 : }
110 89209786 : ineq[k] = status_in(bmap_i->ineq[k], tab_j);
111 89209786 : if (ineq[k] == STATUS_ERROR)
112 0 : goto error;
113 89209786 : if (ineq[k] == STATUS_SEPARATE)
114 11604492 : break;
115 : }
116 :
117 4668350509 : return ineq;
118 : error:
119 0 : free(ineq);
120 0 : return NULL;
121 : }
122 :
123 16339873303 : static int any(int *con, unsigned len, int status)
124 : {
125 : int i;
126 :
127 37507847793 : for (i = 0; i < len ; ++i)
128 23507694290 : if (con[i] == status)
129 2339719800 : return 1;
130 14000153503 : 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 1227850 : static int find(int *con, unsigned len, int status)
137 : {
138 : int i;
139 :
140 4901312 : for (i = 0; i < len ; ++i)
141 4901312 : if (con[i] == status)
142 1227850 : return i;
143 0 : return -1;
144 : }
145 :
146 4137526 : static int count(int *con, unsigned len, int status)
147 : {
148 : int i;
149 4137526 : int c = 0;
150 :
151 35579675 : for (i = 0; i < len ; ++i)
152 31442149 : if (con[i] == status)
153 5074067 : c++;
154 4137526 : return c;
155 : }
156 :
157 2331511019 : static int all(int *con, unsigned len, int status)
158 : {
159 : int i;
160 :
161 4507588842 : for (i = 0; i < len ; ++i) {
162 4504189316 : if (con[i] == STATUS_REDUNDANT)
163 1682763 : continue;
164 4502506553 : if (con[i] != status)
165 2328111493 : return 0;
166 : }
167 3399526 : 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 6994419844 : static int any_eq(struct isl_coalesce_info *info, int status)
207 : {
208 : unsigned n_eq;
209 :
210 6994419844 : n_eq = isl_basic_map_n_equality(info->bmap);
211 6994419844 : 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 9344570469 : static int any_ineq(struct isl_coalesce_info *info, int status)
219 : {
220 : unsigned n_ineq;
221 :
222 9344570469 : n_ineq = isl_basic_map_n_inequality(info->bmap);
223 9344570469 : 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 64536 : static int find_eq(struct isl_coalesce_info *info, int status)
234 : {
235 : unsigned n_eq;
236 :
237 64536 : n_eq = isl_basic_map_n_equality(info->bmap);
238 64536 : 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 1163314 : static int find_ineq(struct isl_coalesce_info *info, int status)
247 : {
248 : unsigned n_ineq;
249 :
250 1163314 : n_ineq = isl_basic_map_n_inequality(info->bmap);
251 1163314 : 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 157389 : static int count_eq(struct isl_coalesce_info *info, int status)
259 : {
260 : unsigned n_eq;
261 :
262 157389 : n_eq = isl_basic_map_n_equality(info->bmap);
263 157389 : 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 3980137 : static int count_ineq(struct isl_coalesce_info *info, int status)
271 : {
272 : unsigned n_ineq;
273 :
274 3980137 : n_ineq = isl_basic_map_n_inequality(info->bmap);
275 3980137 : 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 77969 : static int all_valid_or_cut(struct isl_coalesce_info *info)
282 : {
283 : int i;
284 :
285 307009 : for (i = 0; i < 2 * info->bmap->n_eq; ++i) {
286 229040 : if (info->eq[i] == STATUS_REDUNDANT)
287 0 : continue;
288 229040 : if (info->eq[i] == STATUS_VALID)
289 89967 : continue;
290 139073 : if (info->eq[i] == STATUS_CUT)
291 139073 : continue;
292 0 : return 0;
293 : }
294 :
295 187954 : for (i = 0; i < info->bmap->n_ineq; ++i) {
296 160673 : if (info->ineq[i] == STATUS_REDUNDANT)
297 2975 : continue;
298 157698 : if (info->ineq[i] == STATUS_VALID)
299 16211 : continue;
300 141487 : if (info->ineq[i] == STATUS_CUT)
301 90799 : continue;
302 50688 : return 0;
303 : }
304 :
305 27281 : 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 2898832920 : static int coalesce_info_set_hull_hash(struct isl_coalesce_info *info)
313 : {
314 : isl_basic_map *hull;
315 : unsigned n_div;
316 :
317 2898832920 : hull = isl_basic_map_copy(info->bmap);
318 2898832920 : hull = isl_basic_map_plain_affine_hull(hull);
319 2898832920 : n_div = isl_basic_map_dim(hull, isl_dim_div);
320 2898832920 : hull = isl_basic_map_drop_constraints_involving_dims(hull,
321 : isl_dim_div, 0, n_div);
322 2898832920 : info->hull_hash = isl_basic_map_get_hash(hull);
323 2898832920 : isl_basic_map_free(hull);
324 :
325 2898832920 : return hull ? 0 : -1;
326 : }
327 :
328 : /* Free all the allocated memory in an array
329 : * of "n" isl_coalesce_info elements.
330 : */
331 1208303144 : static void clear_coalesce_info(int n, struct isl_coalesce_info *info)
332 : {
333 : int i;
334 :
335 1208303144 : if (!info)
336 0 : return;
337 :
338 4107136064 : for (i = 0; i < n; ++i) {
339 2898832920 : isl_basic_map_free(info[i].bmap);
340 2898832920 : isl_tab_free(info[i].tab);
341 : }
342 :
343 1208303144 : free(info);
344 : }
345 :
346 : /* Clear the memory associated to "info".
347 : */
348 247424 : static void clear(struct isl_coalesce_info *info)
349 : {
350 247424 : info->bmap = isl_basic_map_free(info->bmap);
351 247424 : isl_tab_free(info->tab);
352 247424 : info->tab = NULL;
353 247424 : }
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 174894 : static void drop(struct isl_coalesce_info *info)
360 : {
361 174894 : clear(info);
362 174894 : info->removed = 1;
363 174894 : }
364 :
365 : /* Exchange the information in "info1" with that in "info2".
366 : */
367 2662 : static void exchange(struct isl_coalesce_info *info1,
368 : struct isl_coalesce_info *info2)
369 : {
370 : struct isl_coalesce_info info;
371 :
372 2662 : info = *info1;
373 2662 : *info1 = *info2;
374 2662 : *info2 = info;
375 2662 : }
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 145060 : 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 145060 : if (!bmap)
427 0 : return NULL;
428 :
429 581899 : for (k = 0; k < info->bmap->n_eq; ++k) {
430 806892 : if (info->eq[2 * k] == STATUS_VALID &&
431 370053 : info->eq[2 * k + 1] == STATUS_VALID) {
432 296818 : l = isl_basic_map_alloc_equality(bmap);
433 296818 : if (l < 0)
434 0 : return isl_basic_map_free(bmap);
435 296818 : isl_seq_cpy(bmap->eq[l], info->bmap->eq[k], len);
436 140021 : } else if (info->eq[2 * k] == STATUS_VALID) {
437 73235 : l = isl_basic_map_alloc_inequality(bmap);
438 73235 : if (l < 0)
439 0 : return isl_basic_map_free(bmap);
440 73235 : isl_seq_neg(bmap->ineq[l], info->bmap->eq[k], len);
441 66786 : } else if (info->eq[2 * k + 1] == STATUS_VALID) {
442 66266 : l = isl_basic_map_alloc_inequality(bmap);
443 66266 : if (l < 0)
444 0 : return isl_basic_map_free(bmap);
445 66266 : isl_seq_cpy(bmap->ineq[l], info->bmap->eq[k], len);
446 : }
447 : }
448 :
449 874117 : for (k = 0; k < info->bmap->n_ineq; ++k) {
450 729057 : if (info->ineq[k] != STATUS_VALID)
451 303574 : continue;
452 425483 : l = isl_basic_map_alloc_inequality(bmap);
453 425483 : if (l < 0)
454 0 : return isl_basic_map_free(bmap);
455 425483 : isl_seq_cpy(bmap->ineq[l], info->bmap->ineq[k], len);
456 : }
457 :
458 145060 : 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 151 : 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 151 : n_old = 2 * info[i].bmap->n_eq + info[i].bmap->n_ineq;
472 151 : n_old += 2 * info[j].bmap->n_eq + info[j].bmap->n_ineq;
473 :
474 151 : n_new = 2 * bmap->n_eq;
475 2893 : for (k = 0; k < bmap->n_ineq; ++k)
476 2742 : if (!isl_tab_is_redundant(tab, bmap->n_eq + k))
477 1311 : ++n_new;
478 :
479 151 : 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 78829 : 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 78829 : struct isl_basic_map *fused = NULL;
503 78829 : struct isl_tab *fused_tab = NULL;
504 78829 : unsigned total = isl_basic_map_total_dim(info[i].bmap);
505 78829 : unsigned extra_rows = extra ? extra->n_row : 0;
506 : unsigned n_eq, n_ineq;
507 78829 : int simplify = 0;
508 :
509 78829 : if (j < i)
510 6299 : return fuse(j, i, info, extra, detect_equalities, check_number);
511 :
512 72530 : n_eq = info[i].bmap->n_eq + info[j].bmap->n_eq;
513 72530 : n_ineq = info[i].bmap->n_ineq + info[j].bmap->n_ineq;
514 145060 : fused = isl_basic_map_alloc_space(isl_space_copy(info[i].bmap->dim),
515 145060 : info[i].bmap->n_div, n_eq, n_eq + n_ineq + extra_rows);
516 72530 : fused = add_valid_constraints(fused, &info[i], 1 + total);
517 72530 : fused = add_valid_constraints(fused, &info[j], 1 + total);
518 72530 : if (!fused)
519 0 : goto error;
520 73008 : if (ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_RATIONAL) &&
521 478 : ISL_F_ISSET(info[j].bmap, ISL_BASIC_MAP_RATIONAL))
522 478 : ISL_F_SET(fused, ISL_BASIC_MAP_RATIONAL);
523 :
524 72530 : for (k = 0; k < info[i].bmap->n_div; ++k) {
525 0 : int l = isl_basic_map_alloc_div(fused);
526 0 : if (l < 0)
527 0 : goto error;
528 0 : if (isl_seq_eq(info[i].bmap->div[k], info[j].bmap->div[k],
529 : 1 + 1 + total)) {
530 0 : 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 225496 : for (k = 0; k < extra_rows; ++k) {
539 152966 : l = isl_basic_map_alloc_inequality(fused);
540 152966 : if (l < 0)
541 0 : goto error;
542 152966 : isl_seq_cpy(fused->ineq[l], extra->row[k], 1 + total);
543 : }
544 :
545 72530 : if (detect_equalities)
546 8619 : fused = isl_basic_map_detect_inequality_pairs(fused, NULL);
547 72530 : fused = isl_basic_map_gauss(fused, NULL);
548 72530 : if (simplify || info[j].simplify) {
549 0 : fused = isl_basic_map_simplify(fused);
550 0 : info[i].simplify = 0;
551 : }
552 72530 : fused = isl_basic_map_finalize(fused);
553 :
554 72530 : fused_tab = isl_tab_from_basic_map(fused, 0);
555 72530 : if (isl_tab_detect_redundant(fused_tab) < 0)
556 0 : goto error;
557 :
558 72681 : if (check_number &&
559 151 : 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 72530 : clear(&info[i]);
566 72530 : info[i].bmap = fused;
567 72530 : info[i].tab = fused_tab;
568 72530 : info[i].modified = 1;
569 72530 : drop(&info[j]);
570 :
571 72530 : 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 11164 : 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 11164 : unsigned n_eq = info[i].bmap->n_eq;
613 :
614 11164 : snap = isl_tab_snap(info[i].tab);
615 11164 : if (isl_tab_mark_rational(info[i].tab) < 0)
616 0 : return isl_change_error;
617 11164 : snap2 = isl_tab_snap(info[i].tab);
618 :
619 25665 : for (k = 0; k < info[i].bmap->n_ineq; ++k) {
620 25183 : if (info[i].ineq[k] != STATUS_CUT)
621 13940 : continue;
622 11243 : if (isl_tab_select_facet(info[i].tab, n_eq + k) < 0)
623 0 : return isl_change_error;
624 31730 : for (l = 0; l < info[j].bmap->n_ineq; ++l) {
625 : int stat;
626 31169 : if (info[j].ineq[l] != STATUS_CUT)
627 18726 : continue;
628 12443 : stat = status_in(info[j].bmap->ineq[l], info[i].tab);
629 12443 : if (stat < 0)
630 0 : return isl_change_error;
631 12443 : if (stat != STATUS_VALID)
632 10682 : break;
633 : }
634 11243 : if (isl_tab_rollback(info[i].tab, snap2) < 0)
635 0 : return isl_change_error;
636 11243 : if (l < info[j].bmap->n_ineq)
637 10682 : break;
638 : }
639 :
640 11164 : if (k < info[i].bmap->n_ineq) {
641 10682 : if (isl_tab_rollback(info[i].tab, snap) < 0)
642 0 : return isl_change_error;
643 10682 : return isl_change_none;
644 : }
645 482 : 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 1055361 : static isl_bool contains(struct isl_coalesce_info *info, struct isl_tab *tab)
655 : {
656 : int k;
657 : unsigned dim;
658 1055361 : isl_basic_map *bmap = info->bmap;
659 :
660 1055361 : dim = isl_basic_map_total_dim(bmap);
661 2262256 : for (k = 0; k < bmap->n_eq; ++k) {
662 : int stat;
663 1415289 : isl_seq_neg(bmap->eq[k], bmap->eq[k], 1 + dim);
664 1415289 : stat = status_in(bmap->eq[k], tab);
665 1415289 : isl_seq_neg(bmap->eq[k], bmap->eq[k], 1 + dim);
666 1415289 : if (stat < 0)
667 0 : return isl_bool_error;
668 1415289 : if (stat != STATUS_VALID)
669 198301 : return isl_bool_false;
670 1216988 : stat = status_in(bmap->eq[k], tab);
671 1216988 : if (stat < 0)
672 0 : return isl_bool_error;
673 1216988 : if (stat != STATUS_VALID)
674 10093 : return isl_bool_false;
675 : }
676 :
677 4064921 : for (k = 0; k < bmap->n_ineq; ++k) {
678 : int stat;
679 4054531 : if (info->ineq[k] == STATUS_REDUNDANT)
680 869387 : continue;
681 3185144 : stat = status_in(bmap->ineq[k], tab);
682 3185144 : if (stat < 0)
683 0 : return isl_bool_error;
684 3185144 : if (stat != STATUS_VALID)
685 836577 : return isl_bool_false;
686 : }
687 10390 : 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 687474 : 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 687474 : unsigned n_eq = info[i].bmap->n_eq;
736 687474 : unsigned total = isl_basic_map_total_dim(info[i].bmap);
737 : isl_stat r;
738 : isl_bool super;
739 :
740 687474 : if (isl_tab_extend_cons(info[i].tab, 1 + info[j].bmap->n_ineq) < 0)
741 0 : return isl_change_error;
742 :
743 687474 : k = find_ineq(&info[i], STATUS_ADJ_INEQ);
744 687474 : 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 687474 : snap = isl_tab_snap(info[i].tab);
750 :
751 687474 : if (isl_tab_unrestrict(info[i].tab, n_eq + k) < 0)
752 0 : return isl_change_error;
753 :
754 687474 : isl_seq_neg(info[i].bmap->ineq[k], info[i].bmap->ineq[k], 1 + total);
755 687474 : isl_int_sub_ui(info[i].bmap->ineq[k][0], info[i].bmap->ineq[k][0], 1);
756 687474 : r = isl_tab_add_ineq(info[i].tab, info[i].bmap->ineq[k]);
757 687474 : isl_seq_neg(info[i].bmap->ineq[k], info[i].bmap->ineq[k], 1 + total);
758 687474 : isl_int_sub_ui(info[i].bmap->ineq[k][0], info[i].bmap->ineq[k][0], 1);
759 687474 : if (r < 0)
760 0 : return isl_change_error;
761 :
762 8387708 : for (k = 0; k < info[j].bmap->n_ineq; ++k) {
763 7700234 : if (info[j].ineq[k] != STATUS_VALID)
764 5108293 : continue;
765 2591941 : if (isl_tab_add_ineq(info[i].tab, info[j].bmap->ineq[k]) < 0)
766 0 : return isl_change_error;
767 : }
768 687474 : if (isl_tab_detect_constants(info[i].tab) < 0)
769 0 : return isl_change_error;
770 :
771 687474 : super = contains(&info[j], info[i].tab);
772 687474 : if (super < 0)
773 0 : return isl_change_error;
774 687474 : if (super)
775 870 : return fuse(i, j, info, NULL, 0, 0);
776 :
777 686604 : if (isl_tab_rollback(info[i].tab, snap) < 0)
778 0 : return isl_change_error;
779 :
780 686604 : 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 1314922 : 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 1314922 : count_i = count_ineq(&info[i], STATUS_ADJ_INEQ);
822 1314922 : count_j = count_ineq(&info[j], STATUS_ADJ_INEQ);
823 :
824 1314922 : if (count_i != 1 && count_j != 1)
825 311729 : return isl_change_none;
826 :
827 1003193 : cut_i = any_eq(&info[i], STATUS_CUT) || any_ineq(&info[i], STATUS_CUT);
828 1003193 : cut_j = any_eq(&info[j], STATUS_CUT) || any_ineq(&info[j], STATUS_CUT);
829 :
830 1003193 : if (!cut_i && !cut_j && count_i == 1 && count_j == 1)
831 25768 : return fuse(i, j, info, NULL, 0, 0);
832 :
833 977425 : if (count_i == 1 && !cut_i)
834 598179 : return is_adj_ineq_extension(i, j, info);
835 :
836 379246 : if (count_j == 1 && !cut_j)
837 89070 : return is_adj_ineq_extension(j, i, info);
838 :
839 290176 : 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 2694232 : static int not_unique_unit_row(__isl_keep isl_mat *T, int row)
851 : {
852 : int i, j;
853 2694232 : int len = T->n_col - 1;
854 :
855 2694232 : i = isl_seq_first_non_zero(T->row[row] + 1, len);
856 2694232 : if (i < 0)
857 327603 : return 1;
858 2431025 : if (!isl_int_is_one(T->row[row][1 + i]) &&
859 64396 : !isl_int_is_negone(T->row[row][1 + i]))
860 59827 : return 1;
861 :
862 2306802 : j = isl_seq_first_non_zero(T->row[row] + 1 + i + 1, len - (i + 1));
863 2306802 : if (j >= 0)
864 2143 : return 1;
865 :
866 19590322 : for (j = 1; j < T->n_row; ++j) {
867 17354573 : if (j == row)
868 2260711 : continue;
869 15093862 : if (!isl_int_is_zero(T->row[j][1 + i]))
870 68910 : return 1;
871 : }
872 :
873 2235749 : 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 430207 : static isl_bool is_affected(__isl_keep isl_basic_map *bmap, int ineq,
882 : int *affected, int total)
883 : {
884 : int i;
885 :
886 2608735 : for (i = 0; i < total; ++i) {
887 2351747 : if (!affected[i])
888 1885312 : continue;
889 466435 : if (!isl_int_is_zero(bmap->ineq[ineq][1 + i]))
890 173219 : return isl_bool_true;
891 : }
892 :
893 256988 : 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 173219 : 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 173219 : if (!v)
923 0 : return NULL;
924 :
925 173219 : ctx = isl_vec_get_ctx(v);
926 173219 : isl_seq_gcd(v->el + 1, v->size - 1, &ctx->normalize_gcd);
927 330719 : if (isl_int_is_zero(ctx->normalize_gcd) ||
928 157500 : isl_int_is_one(ctx->normalize_gcd)) {
929 124838 : return v;
930 : }
931 :
932 48381 : v = isl_vec_cow(v);
933 48381 : if (!v)
934 0 : return NULL;
935 :
936 48381 : isl_int_fdiv_r(v->el[0], v->el[0], ctx->normalize_gcd);
937 48381 : if (isl_int_is_zero(v->el[0]))
938 13654 : return v;
939 :
940 34727 : if (isl_tab_extend_cons(info->tab, 1) < 0)
941 0 : return isl_vec_free(v);
942 :
943 34727 : isl_int_sub(info->bmap->ineq[ineq][0],
944 : info->bmap->ineq[ineq][0], v->el[0]);
945 34727 : r = isl_tab_add_ineq(info->tab, info->bmap->ineq[ineq]);
946 34727 : isl_int_add(info->bmap->ineq[ineq][0],
947 : info->bmap->ineq[ineq][0], v->el[0]);
948 :
949 34727 : if (r < 0)
950 0 : return isl_vec_free(v);
951 :
952 34727 : 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 367887 : 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 367887 : isl_vec *v = NULL;
998 : isl_mat *T;
999 : int i;
1000 : int k;
1001 : int *affected;
1002 :
1003 367887 : k = relaxed[l];
1004 367887 : ctx = isl_basic_map_get_ctx(info->bmap);
1005 367887 : total = isl_basic_map_total_dim(info->bmap);
1006 367887 : isl_int_add_ui(info->bmap->ineq[k][0], info->bmap->ineq[k][0], 1);
1007 367887 : T = isl_mat_sub_alloc6(ctx, info->bmap->ineq, k, 1, 0, 1 + total);
1008 367887 : T = isl_mat_variable_compression(T, NULL);
1009 367887 : isl_int_sub_ui(info->bmap->ineq[k][0], info->bmap->ineq[k][0], 1);
1010 367887 : if (!T)
1011 0 : return isl_stat_error;
1012 367887 : if (T->n_col == 0) {
1013 0 : isl_mat_free(T);
1014 0 : return isl_stat_ok;
1015 : }
1016 :
1017 367887 : affected = isl_alloc_array(ctx, int, total);
1018 367887 : if (!affected)
1019 0 : goto error;
1020 :
1021 3062119 : for (i = 0; i < total; ++i)
1022 2694232 : affected[i] = not_unique_unit_row(T, 1 + i);
1023 :
1024 1250877 : for (i = 0; i < info->bmap->n_ineq; ++i) {
1025 : isl_bool handle;
1026 882990 : if (any(relaxed, n, i))
1027 380091 : continue;
1028 502899 : if (info->ineq[i] == STATUS_REDUNDANT)
1029 72692 : continue;
1030 430207 : handle = is_affected(info->bmap, i, affected, total);
1031 430207 : if (handle < 0)
1032 0 : goto error;
1033 430207 : if (!handle)
1034 256988 : continue;
1035 173219 : v = isl_vec_alloc(ctx, 1 + total);
1036 173219 : if (!v)
1037 0 : goto error;
1038 173219 : isl_seq_cpy(v->el, info->bmap->ineq[i], 1 + total);
1039 173219 : v = isl_vec_mat_product(v, isl_mat_copy(T));
1040 173219 : v = try_tightening(info, i, v);
1041 173219 : isl_vec_free(v);
1042 173219 : if (!v)
1043 0 : goto error;
1044 : }
1045 :
1046 367887 : isl_mat_free(T);
1047 367887 : free(affected);
1048 367887 : 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 9405 : 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 9405 : info[i].bmap = isl_basic_map_cow(info[i].bmap);
1073 9405 : if (!info[i].bmap)
1074 0 : return isl_change_error;
1075 9405 : total = isl_basic_map_total_dim(info[i].bmap);
1076 9405 : for (l = 0; l < info[i].bmap->n_div; ++l)
1077 0 : if (!isl_seq_eq(info[i].bmap->div[l],
1078 0 : 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 18814 : for (l = 0; l < n; ++l)
1083 9409 : isl_int_add_ui(info[i].bmap->ineq[relax[l]][0],
1084 : info[i].bmap->ineq[relax[l]][0], 1);
1085 9405 : ISL_F_CLR(info[i].bmap, ISL_BASIC_MAP_NO_REDUNDANT);
1086 9405 : ISL_F_SET(info[i].bmap, ISL_BASIC_MAP_FINAL);
1087 9405 : drop(&info[j]);
1088 9405 : info[i].modified = 1;
1089 9405 : if (j < i)
1090 2662 : exchange(&info[i], &info[j]);
1091 9405 : 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 367772 : 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 367772 : unsigned n_eq = info[i].bmap->n_eq;
1145 :
1146 747628 : for (l = 0; l < n; ++l)
1147 379856 : if (isl_tab_is_equality(info[i].tab, n_eq + relax[l]))
1148 0 : return isl_change_none;
1149 :
1150 367772 : snap = isl_tab_snap(info[i].tab);
1151 747628 : for (l = 0; l < n; ++l)
1152 379856 : if (isl_tab_relax(info[i].tab, n_eq + relax[l]) < 0)
1153 0 : return isl_change_error;
1154 1495256 : for (l = 0; l < n; ++l) {
1155 379856 : if (!isl_tab_is_redundant(info[i].tab, n_eq + relax[l]))
1156 379856 : 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 367772 : snap2 = isl_tab_snap(info[i].tab);
1162 754584 : for (l = 0; l < n; ++l) {
1163 367887 : if (isl_tab_rollback(info[i].tab, snap2) < 0)
1164 0 : return isl_change_error;
1165 367887 : if (isl_tab_select_facet(info[i].tab, n_eq + relax[l]) < 0)
1166 0 : return isl_change_error;
1167 367887 : if (tighten_on_relaxed_facet(&info[i], n, relax, l) < 0)
1168 0 : return isl_change_error;
1169 367887 : super = contains(&info[j], info[i].tab);
1170 367887 : if (super < 0)
1171 0 : return isl_change_error;
1172 367887 : if (super)
1173 9520 : continue;
1174 358367 : if (isl_tab_rollback(info[i].tab, snap) < 0)
1175 0 : return isl_change_error;
1176 358367 : return isl_change_none;
1177 : }
1178 :
1179 9405 : if (isl_tab_rollback(info[i].tab, snap2) < 0)
1180 0 : return isl_change_error;
1181 9405 : 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 1064582 : 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 1064582 : unsigned total = isl_basic_map_total_dim(info->bmap);
1207 :
1208 1064582 : isl_int_init(max_k);
1209 :
1210 3385039 : for (k = 0; k < info->bmap->n_eq; ++k) {
1211 3876889 : if (info->eq[2 * k] == STATUS_VALID &&
1212 1556432 : info->eq[2 * k + 1] == STATUS_VALID)
1213 1200177 : continue;
1214 1120280 : isl_seq_abs_max(info->bmap->eq[k] + 1, total, &max_k);
1215 1120280 : if (isl_int_abs_gt(max_k, wraps->max))
1216 86455 : isl_int_set(wraps->max, max_k);
1217 : }
1218 :
1219 5121130 : for (k = 0; k < info->bmap->n_ineq; ++k) {
1220 7065584 : if (info->ineq[k] == STATUS_VALID ||
1221 3009036 : info->ineq[k] == STATUS_REDUNDANT)
1222 1759146 : continue;
1223 2297402 : isl_seq_abs_max(info->bmap->ineq[k] + 1, total, &max_k);
1224 2297402 : if (isl_int_abs_gt(max_k, wraps->max))
1225 959052 : isl_int_set(wraps->max, max_k);
1226 : }
1227 :
1228 1064582 : isl_int_clear(max_k);
1229 :
1230 1064582 : 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 532291 : 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 532291 : wraps->bound = 0;
1245 532291 : wraps->mat = mat;
1246 532291 : if (!mat)
1247 0 : return isl_stat_error;
1248 532291 : ctx = isl_mat_get_ctx(mat);
1249 532291 : wraps->bound = isl_options_get_coalesce_bounded_wrapping(ctx);
1250 532291 : if (!wraps->bound)
1251 0 : return isl_stat_ok;
1252 532291 : isl_int_init(wraps->max);
1253 532291 : isl_int_set_si(wraps->max, 0);
1254 532291 : if (wraps_update_max(wraps, &info[i]) < 0)
1255 0 : return isl_stat_error;
1256 532291 : if (wraps_update_max(wraps, &info[j]) < 0)
1257 0 : return isl_stat_error;
1258 :
1259 532291 : return isl_stat_ok;
1260 : }
1261 :
1262 : /* Free the contents of the isl_wraps data structure.
1263 : */
1264 532291 : static void wraps_free(struct isl_wraps *wraps)
1265 : {
1266 532291 : isl_mat_free(wraps->mat);
1267 532291 : if (wraps->bound)
1268 532291 : isl_int_clear(wraps->max);
1269 532291 : }
1270 :
1271 : /* Is the wrapping constraint in row "row" allowed?
1272 : *
1273 : * If wraps->bound is set, we check that none of the coefficients
1274 : * is greater than wraps->max.
1275 : */
1276 176318 : static int allow_wrap(struct isl_wraps *wraps, int row)
1277 : {
1278 : int i;
1279 :
1280 176318 : if (!wraps->bound)
1281 0 : return 1;
1282 :
1283 913855 : for (i = 1; i < wraps->mat->n_col; ++i)
1284 798092 : if (isl_int_abs_gt(wraps->mat->row[row][i], wraps->max))
1285 60555 : return 0;
1286 :
1287 115763 : return 1;
1288 : }
1289 :
1290 : /* Wrap "ineq" (or its opposite if "negate" is set) around "bound"
1291 : * to include "set" and add the result in position "w" of "wraps".
1292 : * "len" is the total number of coefficients in "bound" and "ineq".
1293 : * Return 1 on success, 0 on failure and -1 on error.
1294 : * Wrapping can fail if the result of wrapping is equal to "bound"
1295 : * or if we want to bound the sizes of the coefficients and
1296 : * the wrapped constraint does not satisfy this bound.
1297 : */
1298 602299 : static int add_wrap(struct isl_wraps *wraps, int w, isl_int *bound,
1299 : isl_int *ineq, unsigned len, __isl_keep isl_set *set, int negate)
1300 : {
1301 602299 : isl_seq_cpy(wraps->mat->row[w], bound, len);
1302 602299 : if (negate) {
1303 33959 : isl_seq_neg(wraps->mat->row[w + 1], ineq, len);
1304 33959 : ineq = wraps->mat->row[w + 1];
1305 : }
1306 602299 : if (!isl_set_wrap_facet(set, wraps->mat->row[w], ineq))
1307 0 : return -1;
1308 602299 : if (isl_seq_eq(wraps->mat->row[w], bound, len))
1309 425981 : return 0;
1310 176318 : if (!allow_wrap(wraps, w))
1311 60555 : return 0;
1312 115763 : return 1;
1313 : }
1314 :
1315 : /* For each constraint in info->bmap that is not redundant (as determined
1316 : * by info->tab) and that is not a valid constraint for the other basic map,
1317 : * wrap the constraint around "bound" such that it includes the whole
1318 : * set "set" and append the resulting constraint to "wraps".
1319 : * Note that the constraints that are valid for the other basic map
1320 : * will be added to the combined basic map by default, so there is
1321 : * no need to wrap them.
1322 : * The caller wrap_in_facets even relies on this function not wrapping
1323 : * any constraints that are already valid.
1324 : * "wraps" is assumed to have been pre-allocated to the appropriate size.
1325 : * wraps->n_row is the number of actual wrapped constraints that have
1326 : * been added.
1327 : * If any of the wrapping problems results in a constraint that is
1328 : * identical to "bound", then this means that "set" is unbounded in such
1329 : * way that no wrapping is possible. If this happens then wraps->n_row
1330 : * is reset to zero.
1331 : * Similarly, if we want to bound the coefficients of the wrapping
1332 : * constraints and a newly added wrapping constraint does not
1333 : * satisfy the bound, then wraps->n_row is also reset to zero.
1334 : */
1335 582519 : static isl_stat add_wraps(struct isl_wraps *wraps,
1336 : struct isl_coalesce_info *info, isl_int *bound, __isl_keep isl_set *set)
1337 : {
1338 : int l, m;
1339 : int w;
1340 : int added;
1341 582519 : isl_basic_map *bmap = info->bmap;
1342 582519 : unsigned len = 1 + isl_basic_map_total_dim(bmap);
1343 :
1344 582519 : w = wraps->mat->n_row;
1345 :
1346 1033343 : for (l = 0; l < bmap->n_ineq; ++l) {
1347 1605359 : if (info->ineq[l] == STATUS_VALID ||
1348 678997 : info->ineq[l] == STATUS_REDUNDANT)
1349 396251 : continue;
1350 530111 : if (isl_seq_is_neg(bound, bmap->ineq[l], len))
1351 3213 : continue;
1352 526898 : if (isl_seq_eq(bound, bmap->ineq[l], len))
1353 0 : continue;
1354 526898 : if (isl_tab_is_redundant(info->tab, bmap->n_eq + l))
1355 1393 : continue;
1356 :
1357 525505 : added = add_wrap(wraps, w, bound, bmap->ineq[l], len, set, 0);
1358 525505 : if (added < 0)
1359 0 : return isl_stat_error;
1360 525505 : if (!added)
1361 475538 : goto unbounded;
1362 49967 : ++w;
1363 : }
1364 525637 : for (l = 0; l < bmap->n_eq; ++l) {
1365 429654 : if (isl_seq_is_neg(bound, bmap->eq[l], len))
1366 45837 : continue;
1367 383817 : if (isl_seq_eq(bound, bmap->eq[l], len))
1368 48334 : continue;
1369 :
1370 989711 : for (m = 0; m < 2; ++m) {
1371 665226 : if (info->eq[2 * l + m] == STATUS_VALID)
1372 588432 : continue;
1373 76794 : added = add_wrap(wraps, w, bound, bmap->eq[l], len,
1374 : set, !m);
1375 76794 : if (added < 0)
1376 0 : return isl_stat_error;
1377 76794 : if (!added)
1378 10998 : goto unbounded;
1379 65796 : ++w;
1380 : }
1381 : }
1382 :
1383 95983 : wraps->mat->n_row = w;
1384 95983 : return isl_stat_ok;
1385 : unbounded:
1386 486536 : wraps->mat->n_row = 0;
1387 486536 : return isl_stat_ok;
1388 : }
1389 :
1390 : /* Check if the constraints in "wraps" from "first" until the last
1391 : * are all valid for the basic set represented by "tab".
1392 : * If not, wraps->n_row is set to zero.
1393 : */
1394 4687 : static int check_wraps(__isl_keep isl_mat *wraps, int first,
1395 : struct isl_tab *tab)
1396 : {
1397 : int i;
1398 :
1399 9388 : for (i = first; i < wraps->n_row; ++i) {
1400 : enum isl_ineq_type type;
1401 352 : type = isl_tab_ineq_type(tab, wraps->row[i]);
1402 352 : if (type == isl_ineq_error)
1403 0 : return -1;
1404 352 : if (type == isl_ineq_redundant)
1405 7 : continue;
1406 345 : wraps->n_row = 0;
1407 345 : return 0;
1408 : }
1409 :
1410 4342 : return 0;
1411 : }
1412 :
1413 : /* Return a set that corresponds to the non-redundant constraints
1414 : * (as recorded in tab) of bmap.
1415 : *
1416 : * It's important to remove the redundant constraints as some
1417 : * of the other constraints may have been modified after the
1418 : * constraints were marked redundant.
1419 : * In particular, a constraint may have been relaxed.
1420 : * Redundant constraints are ignored when a constraint is relaxed
1421 : * and should therefore continue to be ignored ever after.
1422 : * Otherwise, the relaxation might be thwarted by some of
1423 : * these constraints.
1424 : *
1425 : * Update the underlying set to ensure that the dimension doesn't change.
1426 : * Otherwise the integer divisions could get dropped if the tab
1427 : * turns out to be empty.
1428 : */
1429 1063262 : static __isl_give isl_set *set_from_updated_bmap(__isl_keep isl_basic_map *bmap,
1430 : struct isl_tab *tab)
1431 : {
1432 : isl_basic_set *bset;
1433 :
1434 1063262 : bmap = isl_basic_map_copy(bmap);
1435 1063262 : bset = isl_basic_map_underlying_set(bmap);
1436 1063262 : bset = isl_basic_set_cow(bset);
1437 1063262 : bset = isl_basic_set_update_from_tab(bset, tab);
1438 1063262 : return isl_set_from_basic_set(bset);
1439 : }
1440 :
1441 : /* Wrap the constraints of info->bmap that bound the facet defined
1442 : * by inequality "k" around (the opposite of) this inequality to
1443 : * include "set". "bound" may be used to store the negated inequality.
1444 : * Since the wrapped constraints are not guaranteed to contain the whole
1445 : * of info->bmap, we check them in check_wraps.
1446 : * If any of the wrapped constraints turn out to be invalid, then
1447 : * check_wraps will reset wrap->n_row to zero.
1448 : */
1449 4687 : static isl_stat add_wraps_around_facet(struct isl_wraps *wraps,
1450 : struct isl_coalesce_info *info, int k, isl_int *bound,
1451 : __isl_keep isl_set *set)
1452 : {
1453 : struct isl_tab_undo *snap;
1454 : int n;
1455 4687 : unsigned total = isl_basic_map_total_dim(info->bmap);
1456 :
1457 4687 : snap = isl_tab_snap(info->tab);
1458 :
1459 4687 : if (isl_tab_select_facet(info->tab, info->bmap->n_eq + k) < 0)
1460 0 : return isl_stat_error;
1461 4687 : if (isl_tab_detect_redundant(info->tab) < 0)
1462 0 : return isl_stat_error;
1463 :
1464 4687 : isl_seq_neg(bound, info->bmap->ineq[k], 1 + total);
1465 :
1466 4687 : n = wraps->mat->n_row;
1467 4687 : if (add_wraps(wraps, info, bound, set) < 0)
1468 0 : return isl_stat_error;
1469 :
1470 4687 : if (isl_tab_rollback(info->tab, snap) < 0)
1471 0 : return isl_stat_error;
1472 4687 : if (check_wraps(wraps->mat, n, info->tab) < 0)
1473 0 : return isl_stat_error;
1474 :
1475 4687 : return isl_stat_ok;
1476 : }
1477 :
1478 : /* Given a basic set i with a constraint k that is adjacent to
1479 : * basic set j, check if we can wrap
1480 : * both the facet corresponding to k (if "wrap_facet" is set) and basic map j
1481 : * (always) around their ridges to include the other set.
1482 : * If so, replace the pair of basic sets by their union.
1483 : *
1484 : * All constraints of i (except k) are assumed to be valid or
1485 : * cut constraints for j.
1486 : * Wrapping the cut constraints to include basic map j may result
1487 : * in constraints that are no longer valid of basic map i
1488 : * we have to check that the resulting wrapping constraints are valid for i.
1489 : * If "wrap_facet" is not set, then all constraints of i (except k)
1490 : * are assumed to be valid for j.
1491 : * ____ _____
1492 : * / | / \
1493 : * / || / |
1494 : * \ || => \ |
1495 : * \ || \ |
1496 : * \___|| \____|
1497 : *
1498 : */
1499 466435 : static enum isl_change can_wrap_in_facet(int i, int j, int k,
1500 : struct isl_coalesce_info *info, int wrap_facet)
1501 : {
1502 466435 : enum isl_change change = isl_change_none;
1503 : struct isl_wraps wraps;
1504 : isl_ctx *ctx;
1505 : isl_mat *mat;
1506 466435 : struct isl_set *set_i = NULL;
1507 466435 : struct isl_set *set_j = NULL;
1508 466435 : struct isl_vec *bound = NULL;
1509 466435 : unsigned total = isl_basic_map_total_dim(info[i].bmap);
1510 :
1511 466435 : set_i = set_from_updated_bmap(info[i].bmap, info[i].tab);
1512 466435 : set_j = set_from_updated_bmap(info[j].bmap, info[j].tab);
1513 466435 : ctx = isl_basic_map_get_ctx(info[i].bmap);
1514 1399305 : mat = isl_mat_alloc(ctx, 2 * (info[i].bmap->n_eq + info[j].bmap->n_eq) +
1515 932870 : info[i].bmap->n_ineq + info[j].bmap->n_ineq,
1516 : 1 + total);
1517 466435 : if (wraps_init(&wraps, mat, info, i, j) < 0)
1518 0 : goto error;
1519 466435 : bound = isl_vec_alloc(ctx, 1 + total);
1520 466435 : if (!set_i || !set_j || !bound)
1521 : goto error;
1522 :
1523 466435 : isl_seq_cpy(bound->el, info[i].bmap->ineq[k], 1 + total);
1524 466435 : isl_int_add_ui(bound->el[0], bound->el[0], 1);
1525 466435 : isl_seq_normalize(ctx, bound->el, 1 + total);
1526 :
1527 466435 : isl_seq_cpy(wraps.mat->row[0], bound->el, 1 + total);
1528 466435 : wraps.mat->n_row = 1;
1529 :
1530 466435 : if (add_wraps(&wraps, &info[j], bound->el, set_i) < 0)
1531 0 : goto error;
1532 466435 : if (!wraps.mat->n_row)
1533 457477 : goto unbounded;
1534 :
1535 8958 : if (wrap_facet) {
1536 4687 : if (add_wraps_around_facet(&wraps, &info[i], k,
1537 : bound->el, set_j) < 0)
1538 0 : goto error;
1539 4687 : if (!wraps.mat->n_row)
1540 4680 : goto unbounded;
1541 : }
1542 :
1543 4278 : change = fuse(i, j, info, wraps.mat, 0, 0);
1544 :
1545 : unbounded:
1546 466435 : wraps_free(&wraps);
1547 :
1548 466435 : isl_set_free(set_i);
1549 466435 : isl_set_free(set_j);
1550 :
1551 466435 : isl_vec_free(bound);
1552 :
1553 466435 : return change;
1554 : error:
1555 0 : wraps_free(&wraps);
1556 0 : isl_vec_free(bound);
1557 0 : isl_set_free(set_i);
1558 0 : isl_set_free(set_j);
1559 0 : return isl_change_error;
1560 : }
1561 :
1562 : /* Given a cut constraint t(x) >= 0 of basic map i, stored in row "w"
1563 : * of wrap.mat, replace it by its relaxed version t(x) + 1 >= 0, and
1564 : * add wrapping constraints to wrap.mat for all constraints
1565 : * of basic map j that bound the part of basic map j that sticks out
1566 : * of the cut constraint.
1567 : * "set_i" is the underlying set of basic map i.
1568 : * If any wrapping fails, then wraps->mat.n_row is reset to zero.
1569 : *
1570 : * In particular, we first intersect basic map j with t(x) + 1 = 0.
1571 : * If the result is empty, then t(x) >= 0 was actually a valid constraint
1572 : * (with respect to the integer points), so we add t(x) >= 0 instead.
1573 : * Otherwise, we wrap the constraints of basic map j that are not
1574 : * redundant in this intersection and that are not already valid
1575 : * for basic map i over basic map i.
1576 : * Note that it is sufficient to wrap the constraints to include
1577 : * basic map i, because we will only wrap the constraints that do
1578 : * not include basic map i already. The wrapped constraint will
1579 : * therefore be more relaxed compared to the original constraint.
1580 : * Since the original constraint is valid for basic map j, so is
1581 : * the wrapped constraint.
1582 : */
1583 2005 : static isl_stat wrap_in_facet(struct isl_wraps *wraps, int w,
1584 : struct isl_coalesce_info *info_j, __isl_keep isl_set *set_i,
1585 : struct isl_tab_undo *snap)
1586 : {
1587 2005 : isl_int_add_ui(wraps->mat->row[w][0], wraps->mat->row[w][0], 1);
1588 2005 : if (isl_tab_add_eq(info_j->tab, wraps->mat->row[w]) < 0)
1589 0 : return isl_stat_error;
1590 2005 : if (isl_tab_detect_redundant(info_j->tab) < 0)
1591 0 : return isl_stat_error;
1592 :
1593 2005 : if (info_j->tab->empty)
1594 0 : isl_int_sub_ui(wraps->mat->row[w][0], wraps->mat->row[w][0], 1);
1595 2005 : else if (add_wraps(wraps, info_j, wraps->mat->row[w], set_i) < 0)
1596 0 : return isl_stat_error;
1597 :
1598 2005 : if (isl_tab_rollback(info_j->tab, snap) < 0)
1599 0 : return isl_stat_error;
1600 :
1601 2005 : return isl_stat_ok;
1602 : }
1603 :
1604 : /* Given a pair of basic maps i and j such that j sticks out
1605 : * of i at n cut constraints, each time by at most one,
1606 : * try to compute wrapping constraints and replace the two
1607 : * basic maps by a single basic map.
1608 : * The other constraints of i are assumed to be valid for j.
1609 : * "set_i" is the underlying set of basic map i.
1610 : * "wraps" has been initialized to be of the right size.
1611 : *
1612 : * For each cut constraint t(x) >= 0 of i, we add the relaxed version
1613 : * t(x) + 1 >= 0, along with wrapping constraints for all constraints
1614 : * of basic map j that bound the part of basic map j that sticks out
1615 : * of the cut constraint.
1616 : *
1617 : * If any wrapping fails, i.e., if we cannot wrap to touch
1618 : * the union, then we give up.
1619 : * Otherwise, the pair of basic maps is replaced by their union.
1620 : */
1621 1320 : static enum isl_change try_wrap_in_facets(int i, int j,
1622 : struct isl_coalesce_info *info, struct isl_wraps *wraps,
1623 : __isl_keep isl_set *set_i)
1624 : {
1625 : int k, l, w;
1626 : unsigned total;
1627 : struct isl_tab_undo *snap;
1628 :
1629 1320 : total = isl_basic_map_total_dim(info[i].bmap);
1630 :
1631 1320 : snap = isl_tab_snap(info[j].tab);
1632 :
1633 1320 : wraps->mat->n_row = 0;
1634 :
1635 2738 : for (k = 0; k < info[i].bmap->n_eq; ++k) {
1636 5384 : for (l = 0; l < 2; ++l) {
1637 3966 : if (info[i].eq[2 * k + l] != STATUS_CUT)
1638 2492 : continue;
1639 1474 : w = wraps->mat->n_row++;
1640 1474 : if (l == 0)
1641 1102 : isl_seq_neg(wraps->mat->row[w],
1642 551 : info[i].bmap->eq[k], 1 + total);
1643 : else
1644 1846 : isl_seq_cpy(wraps->mat->row[w],
1645 923 : info[i].bmap->eq[k], 1 + total);
1646 1474 : if (wrap_in_facet(wraps, w, &info[j], set_i, snap) < 0)
1647 0 : return isl_change_error;
1648 :
1649 1474 : if (!wraps->mat->n_row)
1650 720 : return isl_change_none;
1651 : }
1652 : }
1653 :
1654 3670 : for (k = 0; k < info[i].bmap->n_ineq; ++k) {
1655 3519 : if (info[i].ineq[k] != STATUS_CUT)
1656 2988 : continue;
1657 531 : w = wraps->mat->n_row++;
1658 1062 : isl_seq_cpy(wraps->mat->row[w],
1659 531 : info[i].bmap->ineq[k], 1 + total);
1660 531 : if (wrap_in_facet(wraps, w, &info[j], set_i, snap) < 0)
1661 0 : return isl_change_error;
1662 :
1663 531 : if (!wraps->mat->n_row)
1664 449 : return isl_change_none;
1665 : }
1666 :
1667 151 : return fuse(i, j, info, wraps->mat, 0, 1);
1668 : }
1669 :
1670 : /* Given a pair of basic maps i and j such that j sticks out
1671 : * of i at n cut constraints, each time by at most one,
1672 : * try to compute wrapping constraints and replace the two
1673 : * basic maps by a single basic map.
1674 : * The other constraints of i are assumed to be valid for j.
1675 : *
1676 : * The core computation is performed by try_wrap_in_facets.
1677 : * This function simply extracts an underlying set representation
1678 : * of basic map i and initializes the data structure for keeping
1679 : * track of wrapping constraints.
1680 : */
1681 1320 : static enum isl_change wrap_in_facets(int i, int j, int n,
1682 : struct isl_coalesce_info *info)
1683 : {
1684 1320 : enum isl_change change = isl_change_none;
1685 : struct isl_wraps wraps;
1686 : isl_ctx *ctx;
1687 : isl_mat *mat;
1688 1320 : isl_set *set_i = NULL;
1689 1320 : unsigned total = isl_basic_map_total_dim(info[i].bmap);
1690 : int max_wrap;
1691 :
1692 1320 : if (isl_tab_extend_cons(info[j].tab, 1) < 0)
1693 0 : return isl_change_error;
1694 :
1695 1320 : max_wrap = 1 + 2 * info[j].bmap->n_eq + info[j].bmap->n_ineq;
1696 1320 : max_wrap *= n;
1697 :
1698 1320 : set_i = set_from_updated_bmap(info[i].bmap, info[i].tab);
1699 1320 : ctx = isl_basic_map_get_ctx(info[i].bmap);
1700 1320 : mat = isl_mat_alloc(ctx, max_wrap, 1 + total);
1701 1320 : if (wraps_init(&wraps, mat, info, i, j) < 0)
1702 0 : goto error;
1703 1320 : if (!set_i)
1704 0 : goto error;
1705 :
1706 1320 : change = try_wrap_in_facets(i, j, info, &wraps, set_i);
1707 :
1708 1320 : wraps_free(&wraps);
1709 1320 : isl_set_free(set_i);
1710 :
1711 1320 : return change;
1712 : error:
1713 0 : wraps_free(&wraps);
1714 0 : isl_set_free(set_i);
1715 0 : return isl_change_error;
1716 : }
1717 :
1718 : /* Return the effect of inequality "ineq" on the tableau "tab",
1719 : * after relaxing the constant term of "ineq" by one.
1720 : */
1721 212077 : static enum isl_ineq_type type_of_relaxed(struct isl_tab *tab, isl_int *ineq)
1722 : {
1723 : enum isl_ineq_type type;
1724 :
1725 212077 : isl_int_add_ui(ineq[0], ineq[0], 1);
1726 212077 : type = isl_tab_ineq_type(tab, ineq);
1727 212077 : isl_int_sub_ui(ineq[0], ineq[0], 1);
1728 :
1729 212077 : return type;
1730 : }
1731 :
1732 : /* Given two basic sets i and j,
1733 : * check if relaxing all the cut constraints of i by one turns
1734 : * them into valid constraint for j and check if we can wrap in
1735 : * the bits that are sticking out.
1736 : * If so, replace the pair by their union.
1737 : *
1738 : * We first check if all relaxed cut inequalities of i are valid for j
1739 : * and then try to wrap in the intersections of the relaxed cut inequalities
1740 : * with j.
1741 : *
1742 : * During this wrapping, we consider the points of j that lie at a distance
1743 : * of exactly 1 from i. In particular, we ignore the points that lie in
1744 : * between this lower-dimensional space and the basic map i.
1745 : * We can therefore only apply this to integer maps.
1746 : * ____ _____
1747 : * / ___|_ / \
1748 : * / | | / |
1749 : * \ | | => \ |
1750 : * \|____| \ |
1751 : * \___| \____/
1752 : *
1753 : * _____ ______
1754 : * | ____|_ | \
1755 : * | | | | |
1756 : * | | | => | |
1757 : * |_| | | |
1758 : * |_____| \______|
1759 : *
1760 : * _______
1761 : * | |
1762 : * | |\ |
1763 : * | | \ |
1764 : * | | \ |
1765 : * | | \|
1766 : * | | \
1767 : * | |_____\
1768 : * | |
1769 : * |_______|
1770 : *
1771 : * Wrapping can fail if the result of wrapping one of the facets
1772 : * around its edges does not produce any new facet constraint.
1773 : * In particular, this happens when we try to wrap in unbounded sets.
1774 : *
1775 : * _______________________________________________________________________
1776 : * |
1777 : * | ___
1778 : * | | |
1779 : * |_| |_________________________________________________________________
1780 : * |___|
1781 : *
1782 : * The following is not an acceptable result of coalescing the above two
1783 : * sets as it includes extra integer points.
1784 : * _______________________________________________________________________
1785 : * |
1786 : * |
1787 : * |
1788 : * |
1789 : * \______________________________________________________________________
1790 : */
1791 146677 : static enum isl_change can_wrap_in_set(int i, int j,
1792 : struct isl_coalesce_info *info)
1793 : {
1794 : int k, l;
1795 : int n;
1796 : unsigned total;
1797 :
1798 239530 : if (ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_RATIONAL) ||
1799 92853 : ISL_F_ISSET(info[j].bmap, ISL_BASIC_MAP_RATIONAL))
1800 53824 : return isl_change_none;
1801 :
1802 92853 : n = count_eq(&info[i], STATUS_CUT) + count_ineq(&info[i], STATUS_CUT);
1803 92853 : if (n == 0)
1804 0 : return isl_change_none;
1805 :
1806 92853 : total = isl_basic_map_total_dim(info[i].bmap);
1807 112342 : for (k = 0; k < info[i].bmap->n_eq; ++k) {
1808 120218 : for (l = 0; l < 2; ++l) {
1809 : enum isl_ineq_type type;
1810 :
1811 100729 : if (info[i].eq[2 * k + l] != STATUS_CUT)
1812 39538 : continue;
1813 :
1814 61191 : if (l == 0)
1815 110494 : isl_seq_neg(info[i].bmap->eq[k],
1816 55247 : info[i].bmap->eq[k], 1 + total);
1817 61191 : type = type_of_relaxed(info[j].tab,
1818 61191 : info[i].bmap->eq[k]);
1819 61191 : if (l == 0)
1820 110494 : isl_seq_neg(info[i].bmap->eq[k],
1821 55247 : info[i].bmap->eq[k], 1 + total);
1822 61191 : if (type == isl_ineq_error)
1823 0 : return isl_change_error;
1824 61191 : if (type != isl_ineq_redundant)
1825 57608 : return isl_change_none;
1826 : }
1827 : }
1828 :
1829 114690 : for (k = 0; k < info[i].bmap->n_ineq; ++k) {
1830 : enum isl_ineq_type type;
1831 :
1832 113370 : if (info[i].ineq[k] != STATUS_CUT)
1833 77235 : continue;
1834 :
1835 36135 : type = type_of_relaxed(info[j].tab, info[i].bmap->ineq[k]);
1836 36135 : if (type == isl_ineq_error)
1837 0 : return isl_change_error;
1838 36135 : if (type != isl_ineq_redundant)
1839 33925 : return isl_change_none;
1840 : }
1841 :
1842 1320 : return wrap_in_facets(i, j, n, info);
1843 : }
1844 :
1845 : /* Check if either i or j has only cut constraints that can
1846 : * be used to wrap in (a facet of) the other basic set.
1847 : * if so, replace the pair by their union.
1848 : */
1849 59762 : static enum isl_change check_wrap(int i, int j, struct isl_coalesce_info *info)
1850 : {
1851 59762 : enum isl_change change = isl_change_none;
1852 :
1853 59762 : change = can_wrap_in_set(i, j, info);
1854 59762 : if (change != isl_change_none)
1855 128 : return change;
1856 :
1857 59634 : change = can_wrap_in_set(j, i, info);
1858 59634 : return change;
1859 : }
1860 :
1861 : /* Check if all inequality constraints of "i" that cut "j" cease
1862 : * to be cut constraints if they are relaxed by one.
1863 : * If so, collect the cut constraints in "list".
1864 : * The caller is responsible for allocating "list".
1865 : */
1866 113724 : static isl_bool all_cut_by_one(int i, int j, struct isl_coalesce_info *info,
1867 : int *list)
1868 : {
1869 : int l, n;
1870 :
1871 113724 : n = 0;
1872 365447 : for (l = 0; l < info[i].bmap->n_ineq; ++l) {
1873 : enum isl_ineq_type type;
1874 :
1875 353481 : if (info[i].ineq[l] != STATUS_CUT)
1876 238730 : continue;
1877 114751 : type = type_of_relaxed(info[j].tab, info[i].bmap->ineq[l]);
1878 114751 : if (type == isl_ineq_error)
1879 0 : return isl_bool_error;
1880 114751 : if (type != isl_ineq_redundant)
1881 101758 : return isl_bool_false;
1882 12993 : list[n++] = l;
1883 : }
1884 :
1885 11966 : return isl_bool_true;
1886 : }
1887 :
1888 : /* Given two basic maps such that "j" has at least one equality constraint
1889 : * that is adjacent to an inequality constraint of "i" and such that "i" has
1890 : * exactly one inequality constraint that is adjacent to an equality
1891 : * constraint of "j", check whether "i" can be extended to include "j" or
1892 : * whether "j" can be wrapped into "i".
1893 : * All remaining constraints of "i" and "j" are assumed to be valid
1894 : * or cut constraints of the other basic map.
1895 : * However, none of the equality constraints of "i" are cut constraints.
1896 : *
1897 : * If "i" has any "cut" inequality constraints, then check if relaxing
1898 : * each of them by one is sufficient for them to become valid.
1899 : * If so, check if the inequality constraint adjacent to an equality
1900 : * constraint of "j" along with all these cut constraints
1901 : * can be relaxed by one to contain exactly "j".
1902 : * Otherwise, or if this fails, check if "j" can be wrapped into "i".
1903 : */
1904 469530 : static enum isl_change check_single_adj_eq(int i, int j,
1905 : struct isl_coalesce_info *info)
1906 : {
1907 469530 : enum isl_change change = isl_change_none;
1908 : int k;
1909 : int n_cut;
1910 : int *relax;
1911 : isl_ctx *ctx;
1912 : isl_bool try_relax;
1913 :
1914 469530 : n_cut = count_ineq(&info[i], STATUS_CUT);
1915 :
1916 469530 : k = find_ineq(&info[i], STATUS_ADJ_EQ);
1917 :
1918 469530 : if (n_cut > 0) {
1919 113724 : ctx = isl_basic_map_get_ctx(info[i].bmap);
1920 113724 : relax = isl_calloc_array(ctx, int, 1 + n_cut);
1921 113724 : if (!relax)
1922 0 : return isl_change_error;
1923 113724 : relax[0] = k;
1924 113724 : try_relax = all_cut_by_one(i, j, info, relax + 1);
1925 113724 : if (try_relax < 0)
1926 0 : change = isl_change_error;
1927 : } else {
1928 355806 : try_relax = isl_bool_true;
1929 355806 : relax = &k;
1930 : }
1931 469530 : if (try_relax && change == isl_change_none)
1932 367772 : change = is_relaxed_extension(i, j, 1 + n_cut, relax, info);
1933 469530 : if (n_cut > 0)
1934 113724 : free(relax);
1935 469530 : if (change != isl_change_none)
1936 9405 : return change;
1937 :
1938 460125 : change = can_wrap_in_facet(i, j, k, info, n_cut > 0);
1939 :
1940 460125 : return change;
1941 : }
1942 :
1943 : /* At least one of the basic maps has an equality that is adjacent
1944 : * to an inequality. Make sure that only one of the basic maps has
1945 : * such an equality and that the other basic map has exactly one
1946 : * inequality adjacent to an equality.
1947 : * If the other basic map does not have such an inequality, then
1948 : * check if all its constraints are either valid or cut constraints
1949 : * and, if so, try wrapping in the first map into the second.
1950 : * Otherwise, try to extend one basic map with the other or
1951 : * wrap one basic map in the other.
1952 : */
1953 990770 : static enum isl_change check_adj_eq(int i, int j,
1954 : struct isl_coalesce_info *info)
1955 : {
1956 1201079 : if (any_eq(&info[i], STATUS_ADJ_INEQ) &&
1957 210309 : any_eq(&info[j], STATUS_ADJ_INEQ))
1958 : /* ADJ EQ TOO MANY */
1959 83634 : return isl_change_none;
1960 :
1961 907136 : if (any_eq(&info[i], STATUS_ADJ_INEQ))
1962 126675 : return check_adj_eq(j, i, info);
1963 :
1964 : /* j has an equality adjacent to an inequality in i */
1965 :
1966 780461 : if (count_ineq(&info[i], STATUS_ADJ_EQ) != 1) {
1967 77969 : if (all_valid_or_cut(&info[i]))
1968 27281 : return can_wrap_in_set(i, j, info);
1969 50688 : return isl_change_none;
1970 : }
1971 702492 : if (any_eq(&info[i], STATUS_CUT))
1972 81754 : return isl_change_none;
1973 1241476 : if (any_ineq(&info[j], STATUS_ADJ_EQ) ||
1974 1090272 : any_ineq(&info[i], STATUS_ADJ_INEQ) ||
1975 469534 : any_ineq(&info[j], STATUS_ADJ_INEQ))
1976 : /* ADJ EQ TOO MANY */
1977 151208 : return isl_change_none;
1978 :
1979 469530 : return check_single_adj_eq(i, j, info);
1980 : }
1981 :
1982 : /* Disjunct "j" lies on a hyperplane that is adjacent to disjunct "i".
1983 : * In particular, disjunct "i" has an inequality constraint that is adjacent
1984 : * to a (combination of) equality constraint(s) of disjunct "j",
1985 : * but disjunct "j" has no explicit equality constraint adjacent
1986 : * to an inequality constraint of disjunct "i".
1987 : *
1988 : * Disjunct "i" is already known not to have any equality constraints
1989 : * that are adjacent to an equality or inequality constraint.
1990 : * Check that, other than the inequality constraint mentioned above,
1991 : * all other constraints of disjunct "i" are valid for disjunct "j".
1992 : * If so, try and wrap in disjunct "j".
1993 : */
1994 17471 : static enum isl_change check_ineq_adj_eq(int i, int j,
1995 : struct isl_coalesce_info *info)
1996 : {
1997 : int k;
1998 :
1999 17471 : if (any_eq(&info[i], STATUS_CUT))
2000 1350 : return isl_change_none;
2001 16121 : if (any_ineq(&info[i], STATUS_CUT))
2002 7544 : return isl_change_none;
2003 8577 : if (any_ineq(&info[i], STATUS_ADJ_INEQ))
2004 1128 : return isl_change_none;
2005 7449 : if (count_ineq(&info[i], STATUS_ADJ_EQ) != 1)
2006 1139 : return isl_change_none;
2007 :
2008 6310 : k = find_ineq(&info[i], STATUS_ADJ_EQ);
2009 :
2010 6310 : return can_wrap_in_facet(i, j, k, info, 0);
2011 : }
2012 :
2013 : /* The two basic maps lie on adjacent hyperplanes. In particular,
2014 : * basic map "i" has an equality that lies parallel to basic map "j".
2015 : * Check if we can wrap the facets around the parallel hyperplanes
2016 : * to include the other set.
2017 : *
2018 : * We perform basically the same operations as can_wrap_in_facet,
2019 : * except that we don't need to select a facet of one of the sets.
2020 : * _
2021 : * \\ \\
2022 : * \\ => \\
2023 : * \ \|
2024 : *
2025 : * If there is more than one equality of "i" adjacent to an equality of "j",
2026 : * then the result will satisfy one or more equalities that are a linear
2027 : * combination of these equalities. These will be encoded as pairs
2028 : * of inequalities in the wrapping constraints and need to be made
2029 : * explicit.
2030 : */
2031 64536 : static enum isl_change check_eq_adj_eq(int i, int j,
2032 : struct isl_coalesce_info *info)
2033 : {
2034 : int k;
2035 64536 : enum isl_change change = isl_change_none;
2036 64536 : int detect_equalities = 0;
2037 : struct isl_wraps wraps;
2038 : isl_ctx *ctx;
2039 : isl_mat *mat;
2040 64536 : struct isl_set *set_i = NULL;
2041 64536 : struct isl_set *set_j = NULL;
2042 64536 : struct isl_vec *bound = NULL;
2043 64536 : unsigned total = isl_basic_map_total_dim(info[i].bmap);
2044 :
2045 64536 : if (count_eq(&info[i], STATUS_ADJ_EQ) != 1)
2046 10843 : detect_equalities = 1;
2047 :
2048 64536 : k = find_eq(&info[i], STATUS_ADJ_EQ);
2049 :
2050 64536 : set_i = set_from_updated_bmap(info[i].bmap, info[i].tab);
2051 64536 : set_j = set_from_updated_bmap(info[j].bmap, info[j].tab);
2052 64536 : ctx = isl_basic_map_get_ctx(info[i].bmap);
2053 193608 : mat = isl_mat_alloc(ctx, 2 * (info[i].bmap->n_eq + info[j].bmap->n_eq) +
2054 129072 : info[i].bmap->n_ineq + info[j].bmap->n_ineq,
2055 : 1 + total);
2056 64536 : if (wraps_init(&wraps, mat, info, i, j) < 0)
2057 0 : goto error;
2058 64536 : bound = isl_vec_alloc(ctx, 1 + total);
2059 64536 : if (!set_i || !set_j || !bound)
2060 : goto error;
2061 :
2062 64536 : if (k % 2 == 0)
2063 23073 : isl_seq_neg(bound->el, info[i].bmap->eq[k / 2], 1 + total);
2064 : else
2065 41463 : isl_seq_cpy(bound->el, info[i].bmap->eq[k / 2], 1 + total);
2066 64536 : isl_int_add_ui(bound->el[0], bound->el[0], 1);
2067 :
2068 64536 : isl_seq_cpy(wraps.mat->row[0], bound->el, 1 + total);
2069 64536 : wraps.mat->n_row = 1;
2070 :
2071 64536 : if (add_wraps(&wraps, &info[j], bound->el, set_i) < 0)
2072 0 : goto error;
2073 64536 : if (!wraps.mat->n_row)
2074 19680 : goto unbounded;
2075 :
2076 44856 : isl_int_sub_ui(bound->el[0], bound->el[0], 1);
2077 44856 : isl_seq_neg(bound->el, bound->el, 1 + total);
2078 :
2079 44856 : isl_seq_cpy(wraps.mat->row[wraps.mat->n_row], bound->el, 1 + total);
2080 44856 : wraps.mat->n_row++;
2081 :
2082 44856 : if (add_wraps(&wraps, &info[i], bound->el, set_j) < 0)
2083 0 : goto error;
2084 44856 : if (!wraps.mat->n_row)
2085 3875 : goto unbounded;
2086 :
2087 40981 : change = fuse(i, j, info, wraps.mat, detect_equalities, 0);
2088 :
2089 : if (0) {
2090 0 : error: change = isl_change_error;
2091 : }
2092 : unbounded:
2093 :
2094 64536 : wraps_free(&wraps);
2095 64536 : isl_set_free(set_i);
2096 64536 : isl_set_free(set_j);
2097 64536 : isl_vec_free(bound);
2098 :
2099 64536 : return change;
2100 : }
2101 :
2102 : /* Initialize the "eq" and "ineq" fields of "info".
2103 : */
2104 4674949870 : static void init_status(struct isl_coalesce_info *info)
2105 : {
2106 4674949870 : info->eq = info->ineq = NULL;
2107 4674949870 : }
2108 :
2109 : /* Set info->eq to the positions of the equalities of info->bmap
2110 : * with respect to the basic map represented by "tab".
2111 : * If info->eq has already been computed, then do not compute it again.
2112 : */
2113 4651740886 : static void set_eq_status_in(struct isl_coalesce_info *info,
2114 : struct isl_tab *tab)
2115 : {
2116 4651740886 : if (info->eq)
2117 0 : return;
2118 4651740886 : info->eq = eq_status_in(info->bmap, tab);
2119 : }
2120 :
2121 : /* Set info->ineq to the positions of the inequalities of info->bmap
2122 : * with respect to the basic map represented by "tab".
2123 : * If info->ineq has already been computed, then do not compute it again.
2124 : */
2125 4668350509 : static void set_ineq_status_in(struct isl_coalesce_info *info,
2126 : struct isl_tab *tab)
2127 : {
2128 4668350509 : if (info->ineq)
2129 0 : return;
2130 4668350509 : info->ineq = ineq_status_in(info->bmap, info->tab, tab);
2131 : }
2132 :
2133 : /* Free the memory allocated by the "eq" and "ineq" fields of "info".
2134 : * This function assumes that init_status has been called on "info" first,
2135 : * after which the "eq" and "ineq" fields may or may not have been
2136 : * assigned a newly allocated array.
2137 : */
2138 4674949870 : static void clear_status(struct isl_coalesce_info *info)
2139 : {
2140 4674949870 : free(info->eq);
2141 4674949870 : free(info->ineq);
2142 4674949870 : }
2143 :
2144 : /* Are all inequality constraints of the basic map represented by "info"
2145 : * valid for the other basic map, except for a single constraint
2146 : * that is adjacent to an inequality constraint of the other basic map?
2147 : */
2148 35697 : static int all_ineq_valid_or_single_adj_ineq(struct isl_coalesce_info *info)
2149 : {
2150 : int i;
2151 35697 : int k = -1;
2152 :
2153 116198 : for (i = 0; i < info->bmap->n_ineq; ++i) {
2154 115973 : if (info->ineq[i] == STATUS_REDUNDANT)
2155 29173 : continue;
2156 86800 : if (info->ineq[i] == STATUS_VALID)
2157 39242 : continue;
2158 47558 : if (info->ineq[i] != STATUS_ADJ_INEQ)
2159 34260 : return 0;
2160 13298 : if (k != -1)
2161 1212 : return 0;
2162 12086 : k = i;
2163 : }
2164 :
2165 225 : return k != -1;
2166 : }
2167 :
2168 : /* Basic map "i" has one or more equality constraints that separate it
2169 : * from basic map "j". Check if it happens to be an extension
2170 : * of basic map "j".
2171 : * In particular, check that all constraints of "j" are valid for "i",
2172 : * except for one inequality constraint that is adjacent
2173 : * to an inequality constraints of "i".
2174 : * If so, check for "i" being an extension of "j" by calling
2175 : * is_adj_ineq_extension.
2176 : *
2177 : * Clean up the memory allocated for keeping track of the status
2178 : * of the constraints before returning.
2179 : */
2180 2323495033 : static enum isl_change separating_equality(int i, int j,
2181 : struct isl_coalesce_info *info)
2182 : {
2183 2323495033 : enum isl_change change = isl_change_none;
2184 :
2185 2323530730 : if (all(info[j].eq, 2 * info[j].bmap->n_eq, STATUS_VALID) &&
2186 35697 : all_ineq_valid_or_single_adj_ineq(&info[j]))
2187 225 : change = is_adj_ineq_extension(j, i, info);
2188 :
2189 2323495033 : clear_status(&info[i]);
2190 2323495033 : clear_status(&info[j]);
2191 2323495033 : return change;
2192 : }
2193 :
2194 : /* Check if the union of the given pair of basic maps
2195 : * can be represented by a single basic map.
2196 : * If so, replace the pair by the single basic map and return
2197 : * isl_change_drop_first, isl_change_drop_second or isl_change_fuse.
2198 : * Otherwise, return isl_change_none.
2199 : * The two basic maps are assumed to live in the same local space.
2200 : * The "eq" and "ineq" fields of info[i] and info[j] are assumed
2201 : * to have been initialized by the caller, either to NULL or
2202 : * to valid information.
2203 : *
2204 : * We first check the effect of each constraint of one basic map
2205 : * on the other basic map.
2206 : * The constraint may be
2207 : * redundant the constraint is redundant in its own
2208 : * basic map and should be ignore and removed
2209 : * in the end
2210 : * valid all (integer) points of the other basic map
2211 : * satisfy the constraint
2212 : * separate no (integer) point of the other basic map
2213 : * satisfies the constraint
2214 : * cut some but not all points of the other basic map
2215 : * satisfy the constraint
2216 : * adj_eq the given constraint is adjacent (on the outside)
2217 : * to an equality of the other basic map
2218 : * adj_ineq the given constraint is adjacent (on the outside)
2219 : * to an inequality of the other basic map
2220 : *
2221 : * We consider seven cases in which we can replace the pair by a single
2222 : * basic map. We ignore all "redundant" constraints.
2223 : *
2224 : * 1. all constraints of one basic map are valid
2225 : * => the other basic map is a subset and can be removed
2226 : *
2227 : * 2. all constraints of both basic maps are either "valid" or "cut"
2228 : * and the facets corresponding to the "cut" constraints
2229 : * of one of the basic maps lies entirely inside the other basic map
2230 : * => the pair can be replaced by a basic map consisting
2231 : * of the valid constraints in both basic maps
2232 : *
2233 : * 3. there is a single pair of adjacent inequalities
2234 : * (all other constraints are "valid")
2235 : * => the pair can be replaced by a basic map consisting
2236 : * of the valid constraints in both basic maps
2237 : *
2238 : * 4. one basic map has a single adjacent inequality, while the other
2239 : * constraints are "valid". The other basic map has some
2240 : * "cut" constraints, but replacing the adjacent inequality by
2241 : * its opposite and adding the valid constraints of the other
2242 : * basic map results in a subset of the other basic map
2243 : * => the pair can be replaced by a basic map consisting
2244 : * of the valid constraints in both basic maps
2245 : *
2246 : * 5. there is a single adjacent pair of an inequality and an equality,
2247 : * the other constraints of the basic map containing the inequality are
2248 : * "valid". Moreover, if the inequality the basic map is relaxed
2249 : * and then turned into an equality, then resulting facet lies
2250 : * entirely inside the other basic map
2251 : * => the pair can be replaced by the basic map containing
2252 : * the inequality, with the inequality relaxed.
2253 : *
2254 : * 6. there is a single inequality adjacent to an equality,
2255 : * the other constraints of the basic map containing the inequality are
2256 : * "valid". Moreover, the facets corresponding to both
2257 : * the inequality and the equality can be wrapped around their
2258 : * ridges to include the other basic map
2259 : * => the pair can be replaced by a basic map consisting
2260 : * of the valid constraints in both basic maps together
2261 : * with all wrapping constraints
2262 : *
2263 : * 7. one of the basic maps extends beyond the other by at most one.
2264 : * Moreover, the facets corresponding to the cut constraints and
2265 : * the pieces of the other basic map at offset one from these cut
2266 : * constraints can be wrapped around their ridges to include
2267 : * the union of the two basic maps
2268 : * => the pair can be replaced by a basic map consisting
2269 : * of the valid constraints in both basic maps together
2270 : * with all wrapping constraints
2271 : *
2272 : * 8. the two basic maps live in adjacent hyperplanes. In principle
2273 : * such sets can always be combined through wrapping, but we impose
2274 : * that there is only one such pair, to avoid overeager coalescing.
2275 : *
2276 : * Throughout the computation, we maintain a collection of tableaus
2277 : * corresponding to the basic maps. When the basic maps are dropped
2278 : * or combined, the tableaus are modified accordingly.
2279 : */
2280 2337474935 : static enum isl_change coalesce_local_pair_reuse(int i, int j,
2281 : struct isl_coalesce_info *info)
2282 : {
2283 2337474935 : enum isl_change change = isl_change_none;
2284 :
2285 2337474935 : set_ineq_status_in(&info[i], info[j].tab);
2286 2337474935 : if (info[i].bmap->n_ineq && !info[i].ineq)
2287 0 : goto error;
2288 2337474935 : if (any_ineq(&info[i], STATUS_ERROR))
2289 0 : goto error;
2290 2337474935 : if (any_ineq(&info[i], STATUS_SEPARATE))
2291 6599361 : goto done;
2292 :
2293 2330875574 : set_ineq_status_in(&info[j], info[i].tab);
2294 2330875574 : if (info[j].bmap->n_ineq && !info[j].ineq)
2295 0 : goto error;
2296 2330875574 : if (any_ineq(&info[j], STATUS_ERROR))
2297 0 : goto error;
2298 2330875574 : if (any_ineq(&info[j], STATUS_SEPARATE))
2299 5005131 : goto done;
2300 :
2301 2325870443 : set_eq_status_in(&info[i], info[j].tab);
2302 2325870443 : if (info[i].bmap->n_eq && !info[i].eq)
2303 0 : goto error;
2304 2325870443 : if (any_eq(&info[i], STATUS_ERROR))
2305 0 : goto error;
2306 :
2307 2325870443 : set_eq_status_in(&info[j], info[i].tab);
2308 2325870443 : if (info[j].bmap->n_eq && !info[j].eq)
2309 0 : goto error;
2310 2325870443 : if (any_eq(&info[j], STATUS_ERROR))
2311 0 : goto error;
2312 :
2313 2325870443 : if (any_eq(&info[i], STATUS_SEPARATE))
2314 2322862258 : return separating_equality(i, j, info);
2315 3008185 : if (any_eq(&info[j], STATUS_SEPARATE))
2316 632775 : return separating_equality(j, i, info);
2317 :
2318 4311141 : if (all(info[i].eq, 2 * info[i].bmap->n_eq, STATUS_VALID) &&
2319 1935731 : all(info[i].ineq, info[i].bmap->n_ineq, STATUS_VALID)) {
2320 44521 : drop(&info[j]);
2321 44521 : change = isl_change_drop_second;
2322 3704845 : } else if (all(info[j].eq, 2 * info[j].bmap->n_eq, STATUS_VALID) &&
2323 1373956 : all(info[j].ineq, info[j].bmap->n_ineq, STATUS_VALID)) {
2324 9621 : drop(&info[i]);
2325 9621 : change = isl_change_drop_first;
2326 2321268 : } else if (any_eq(&info[i], STATUS_ADJ_EQ)) {
2327 60140 : change = check_eq_adj_eq(i, j, info);
2328 2261128 : } else if (any_eq(&info[j], STATUS_ADJ_EQ)) {
2329 4396 : change = check_eq_adj_eq(j, i, info);
2330 4303155 : } else if (any_eq(&info[i], STATUS_ADJ_INEQ) ||
2331 2046423 : any_eq(&info[j], STATUS_ADJ_INEQ)) {
2332 864095 : change = check_adj_eq(i, j, info);
2333 1392637 : } else if (any_ineq(&info[i], STATUS_ADJ_EQ)) {
2334 12841 : change = check_ineq_adj_eq(i, j, info);
2335 1379796 : } else if (any_ineq(&info[j], STATUS_ADJ_EQ)) {
2336 4630 : change = check_ineq_adj_eq(j, i, info);
2337 1445590 : } else if (any_ineq(&info[i], STATUS_ADJ_INEQ) ||
2338 70424 : any_ineq(&info[j], STATUS_ADJ_INEQ)) {
2339 1314922 : change = check_adj_ineq(i, j, info);
2340 : } else {
2341 80215 : if (!any_eq(&info[i], STATUS_CUT) &&
2342 19971 : !any_eq(&info[j], STATUS_CUT))
2343 11164 : change = check_facets(i, j, info);
2344 60244 : if (change == isl_change_none)
2345 59762 : change = check_wrap(i, j, info);
2346 : }
2347 :
2348 : done:
2349 13979902 : clear_status(&info[i]);
2350 13979902 : clear_status(&info[j]);
2351 13979902 : return change;
2352 : error:
2353 0 : clear_status(&info[i]);
2354 0 : clear_status(&info[j]);
2355 0 : return isl_change_error;
2356 : }
2357 :
2358 : /* Check if the union of the given pair of basic maps
2359 : * can be represented by a single basic map.
2360 : * If so, replace the pair by the single basic map and return
2361 : * isl_change_drop_first, isl_change_drop_second or isl_change_fuse.
2362 : * Otherwise, return isl_change_none.
2363 : * The two basic maps are assumed to live in the same local space.
2364 : */
2365 2337474935 : static enum isl_change coalesce_local_pair(int i, int j,
2366 : struct isl_coalesce_info *info)
2367 : {
2368 2337474935 : init_status(&info[i]);
2369 2337474935 : init_status(&info[j]);
2370 2337474935 : return coalesce_local_pair_reuse(i, j, info);
2371 : }
2372 :
2373 : /* Shift the integer division at position "div" of the basic map
2374 : * represented by "info" by "shift".
2375 : *
2376 : * That is, if the integer division has the form
2377 : *
2378 : * floor(f(x)/d)
2379 : *
2380 : * then replace it by
2381 : *
2382 : * floor((f(x) + shift * d)/d) - shift
2383 : */
2384 0 : static isl_stat shift_div(struct isl_coalesce_info *info, int div,
2385 : isl_int shift)
2386 : {
2387 : unsigned total;
2388 :
2389 0 : info->bmap = isl_basic_map_shift_div(info->bmap, div, 0, shift);
2390 0 : if (!info->bmap)
2391 0 : return isl_stat_error;
2392 :
2393 0 : total = isl_basic_map_dim(info->bmap, isl_dim_all);
2394 0 : total -= isl_basic_map_dim(info->bmap, isl_dim_div);
2395 0 : if (isl_tab_shift_var(info->tab, total + div, shift) < 0)
2396 0 : return isl_stat_error;
2397 :
2398 0 : return isl_stat_ok;
2399 : }
2400 :
2401 : /* If the integer division at position "div" is defined by an equality,
2402 : * i.e., a stride constraint, then change the integer division expression
2403 : * to have a constant term equal to zero.
2404 : *
2405 : * Let the equality constraint be
2406 : *
2407 : * c + f + m a = 0
2408 : *
2409 : * The integer division expression is then typically of the form
2410 : *
2411 : * a = floor((-f - c')/m)
2412 : *
2413 : * The integer division is first shifted by t = floor(c/m),
2414 : * turning the equality constraint into
2415 : *
2416 : * c - m floor(c/m) + f + m a' = 0
2417 : *
2418 : * i.e.,
2419 : *
2420 : * (c mod m) + f + m a' = 0
2421 : *
2422 : * That is,
2423 : *
2424 : * a' = (-f - (c mod m))/m = floor((-f)/m)
2425 : *
2426 : * because a' is an integer and 0 <= (c mod m) < m.
2427 : * The constant term of a' can therefore be zeroed out,
2428 : * but only if the integer division expression is of the expected form.
2429 : */
2430 0 : static isl_stat normalize_stride_div(struct isl_coalesce_info *info, int div)
2431 : {
2432 : isl_bool defined, valid;
2433 : isl_stat r;
2434 : isl_constraint *c;
2435 : isl_int shift, stride;
2436 :
2437 0 : defined = isl_basic_map_has_defining_equality(info->bmap, isl_dim_div,
2438 : div, &c);
2439 0 : if (defined < 0)
2440 0 : return isl_stat_error;
2441 0 : if (!defined)
2442 0 : return isl_stat_ok;
2443 0 : if (!c)
2444 0 : return isl_stat_error;
2445 0 : valid = isl_constraint_is_div_equality(c, div);
2446 0 : isl_int_init(shift);
2447 0 : isl_int_init(stride);
2448 0 : isl_constraint_get_constant(c, &shift);
2449 0 : isl_constraint_get_coefficient(c, isl_dim_div, div, &stride);
2450 0 : isl_int_fdiv_q(shift, shift, stride);
2451 0 : r = shift_div(info, div, shift);
2452 0 : isl_int_clear(stride);
2453 0 : isl_int_clear(shift);
2454 0 : isl_constraint_free(c);
2455 0 : if (r < 0 || valid < 0)
2456 0 : return isl_stat_error;
2457 0 : if (!valid)
2458 0 : return isl_stat_ok;
2459 0 : info->bmap = isl_basic_map_set_div_expr_constant_num_si_inplace(
2460 : info->bmap, div, 0);
2461 0 : if (!info->bmap)
2462 0 : return isl_stat_error;
2463 0 : return isl_stat_ok;
2464 : }
2465 :
2466 : /* The basic maps represented by "info1" and "info2" are known
2467 : * to have the same number of integer divisions.
2468 : * Check if pairs of integer divisions are equal to each other
2469 : * despite the fact that they differ by a rational constant.
2470 : *
2471 : * In particular, look for any pair of integer divisions that
2472 : * only differ in their constant terms.
2473 : * If either of these integer divisions is defined
2474 : * by stride constraints, then modify it to have a zero constant term.
2475 : * If both are defined by stride constraints then in the end they will have
2476 : * the same (zero) constant term.
2477 : */
2478 0 : static isl_stat harmonize_stride_divs(struct isl_coalesce_info *info1,
2479 : struct isl_coalesce_info *info2)
2480 : {
2481 : int i, n;
2482 :
2483 0 : n = isl_basic_map_dim(info1->bmap, isl_dim_div);
2484 0 : for (i = 0; i < n; ++i) {
2485 : isl_bool known, harmonize;
2486 :
2487 0 : known = isl_basic_map_div_is_known(info1->bmap, i);
2488 0 : if (known >= 0 && known)
2489 0 : known = isl_basic_map_div_is_known(info2->bmap, i);
2490 0 : if (known < 0)
2491 0 : return isl_stat_error;
2492 0 : if (!known)
2493 0 : continue;
2494 0 : harmonize = isl_basic_map_equal_div_expr_except_constant(
2495 : info1->bmap, i, info2->bmap, i);
2496 0 : if (harmonize < 0)
2497 0 : return isl_stat_error;
2498 0 : if (!harmonize)
2499 0 : continue;
2500 0 : if (normalize_stride_div(info1, i) < 0)
2501 0 : return isl_stat_error;
2502 0 : if (normalize_stride_div(info2, i) < 0)
2503 0 : return isl_stat_error;
2504 : }
2505 :
2506 0 : return isl_stat_ok;
2507 : }
2508 :
2509 : /* If "shift" is an integer constant, then shift the integer division
2510 : * at position "div" of the basic map represented by "info" by "shift".
2511 : * If "shift" is not an integer constant, then do nothing.
2512 : * If "shift" is equal to zero, then no shift needs to be performed either.
2513 : *
2514 : * That is, if the integer division has the form
2515 : *
2516 : * floor(f(x)/d)
2517 : *
2518 : * then replace it by
2519 : *
2520 : * floor((f(x) + shift * d)/d) - shift
2521 : */
2522 0 : static isl_stat shift_if_cst_int(struct isl_coalesce_info *info, int div,
2523 : __isl_keep isl_aff *shift)
2524 : {
2525 : isl_bool cst;
2526 : isl_stat r;
2527 : isl_int d;
2528 : isl_val *c;
2529 :
2530 0 : cst = isl_aff_is_cst(shift);
2531 0 : if (cst < 0 || !cst)
2532 0 : return cst < 0 ? isl_stat_error : isl_stat_ok;
2533 :
2534 0 : c = isl_aff_get_constant_val(shift);
2535 0 : cst = isl_val_is_int(c);
2536 0 : if (cst >= 0 && cst)
2537 0 : cst = isl_bool_not(isl_val_is_zero(c));
2538 0 : if (cst < 0 || !cst) {
2539 0 : isl_val_free(c);
2540 0 : return cst < 0 ? isl_stat_error : isl_stat_ok;
2541 : }
2542 :
2543 0 : isl_int_init(d);
2544 0 : r = isl_val_get_num_isl_int(c, &d);
2545 0 : if (r >= 0)
2546 0 : r = shift_div(info, div, d);
2547 0 : isl_int_clear(d);
2548 :
2549 0 : isl_val_free(c);
2550 :
2551 0 : return r;
2552 : }
2553 :
2554 : /* Check if some of the divs in the basic map represented by "info1"
2555 : * are shifts of the corresponding divs in the basic map represented
2556 : * by "info2", taking into account the equality constraints "eq1" of "info1"
2557 : * and "eq2" of "info2". If so, align them with those of "info2".
2558 : * "info1" and "info2" are assumed to have the same number
2559 : * of integer divisions.
2560 : *
2561 : * An integer division is considered to be a shift of another integer
2562 : * division if, after simplification with respect to the equality
2563 : * constraints of the other basic map, one is equal to the other
2564 : * plus a constant.
2565 : *
2566 : * In particular, for each pair of integer divisions, if both are known,
2567 : * have the same denominator and are not already equal to each other,
2568 : * simplify each with respect to the equality constraints
2569 : * of the other basic map. If the difference is an integer constant,
2570 : * then move this difference outside.
2571 : * That is, if, after simplification, one integer division is of the form
2572 : *
2573 : * floor((f(x) + c_1)/d)
2574 : *
2575 : * while the other is of the form
2576 : *
2577 : * floor((f(x) + c_2)/d)
2578 : *
2579 : * and n = (c_2 - c_1)/d is an integer, then replace the first
2580 : * integer division by
2581 : *
2582 : * floor((f_1(x) + c_1 + n * d)/d) - n,
2583 : *
2584 : * where floor((f_1(x) + c_1 + n * d)/d) = floor((f2(x) + c_2)/d)
2585 : * after simplification with respect to the equality constraints.
2586 : */
2587 0 : static isl_stat harmonize_divs_with_hulls(struct isl_coalesce_info *info1,
2588 : struct isl_coalesce_info *info2, __isl_keep isl_basic_set *eq1,
2589 : __isl_keep isl_basic_set *eq2)
2590 : {
2591 : int i;
2592 : int total;
2593 : isl_local_space *ls1, *ls2;
2594 :
2595 0 : total = isl_basic_map_total_dim(info1->bmap);
2596 0 : ls1 = isl_local_space_wrap(isl_basic_map_get_local_space(info1->bmap));
2597 0 : ls2 = isl_local_space_wrap(isl_basic_map_get_local_space(info2->bmap));
2598 0 : for (i = 0; i < info1->bmap->n_div; ++i) {
2599 : isl_stat r;
2600 : isl_aff *div1, *div2;
2601 :
2602 0 : if (!isl_local_space_div_is_known(ls1, i) ||
2603 0 : !isl_local_space_div_is_known(ls2, i))
2604 0 : continue;
2605 0 : if (isl_int_ne(info1->bmap->div[i][0], info2->bmap->div[i][0]))
2606 0 : continue;
2607 0 : if (isl_seq_eq(info1->bmap->div[i] + 1,
2608 0 : info2->bmap->div[i] + 1, 1 + total))
2609 0 : continue;
2610 0 : div1 = isl_local_space_get_div(ls1, i);
2611 0 : div2 = isl_local_space_get_div(ls2, i);
2612 0 : div1 = isl_aff_substitute_equalities(div1,
2613 : isl_basic_set_copy(eq2));
2614 0 : div2 = isl_aff_substitute_equalities(div2,
2615 : isl_basic_set_copy(eq1));
2616 0 : div2 = isl_aff_sub(div2, div1);
2617 0 : r = shift_if_cst_int(info1, i, div2);
2618 0 : isl_aff_free(div2);
2619 0 : if (r < 0)
2620 0 : break;
2621 : }
2622 0 : isl_local_space_free(ls1);
2623 0 : isl_local_space_free(ls2);
2624 :
2625 0 : if (i < info1->bmap->n_div)
2626 0 : return isl_stat_error;
2627 0 : return isl_stat_ok;
2628 : }
2629 :
2630 : /* Check if some of the divs in the basic map represented by "info1"
2631 : * are shifts of the corresponding divs in the basic map represented
2632 : * by "info2". If so, align them with those of "info2".
2633 : * Only do this if "info1" and "info2" have the same number
2634 : * of integer divisions.
2635 : *
2636 : * An integer division is considered to be a shift of another integer
2637 : * division if, after simplification with respect to the equality
2638 : * constraints of the other basic map, one is equal to the other
2639 : * plus a constant.
2640 : *
2641 : * First check if pairs of integer divisions are equal to each other
2642 : * despite the fact that they differ by a rational constant.
2643 : * If so, try and arrange for them to have the same constant term.
2644 : *
2645 : * Then, extract the equality constraints and continue with
2646 : * harmonize_divs_with_hulls.
2647 : *
2648 : * If the equality constraints of both basic maps are the same,
2649 : * then there is no need to perform any shifting since
2650 : * the coefficients of the integer divisions should have been
2651 : * reduced in the same way.
2652 : */
2653 2337474935 : static isl_stat harmonize_divs(struct isl_coalesce_info *info1,
2654 : struct isl_coalesce_info *info2)
2655 : {
2656 : isl_bool equal;
2657 : isl_basic_map *bmap1, *bmap2;
2658 : isl_basic_set *eq1, *eq2;
2659 : isl_stat r;
2660 :
2661 2337474935 : if (!info1->bmap || !info2->bmap)
2662 0 : return isl_stat_error;
2663 :
2664 2337474935 : if (info1->bmap->n_div != info2->bmap->n_div)
2665 0 : return isl_stat_ok;
2666 2337474935 : if (info1->bmap->n_div == 0)
2667 2337474935 : return isl_stat_ok;
2668 :
2669 0 : if (harmonize_stride_divs(info1, info2) < 0)
2670 0 : return isl_stat_error;
2671 :
2672 0 : bmap1 = isl_basic_map_copy(info1->bmap);
2673 0 : bmap2 = isl_basic_map_copy(info2->bmap);
2674 0 : eq1 = isl_basic_map_wrap(isl_basic_map_plain_affine_hull(bmap1));
2675 0 : eq2 = isl_basic_map_wrap(isl_basic_map_plain_affine_hull(bmap2));
2676 0 : equal = isl_basic_set_plain_is_equal(eq1, eq2);
2677 0 : if (equal < 0)
2678 0 : r = isl_stat_error;
2679 0 : else if (equal)
2680 0 : r = isl_stat_ok;
2681 : else
2682 0 : r = harmonize_divs_with_hulls(info1, info2, eq1, eq2);
2683 0 : isl_basic_set_free(eq1);
2684 0 : isl_basic_set_free(eq2);
2685 :
2686 0 : return r;
2687 : }
2688 :
2689 : /* Do the two basic maps live in the same local space, i.e.,
2690 : * do they have the same (known) divs?
2691 : * If either basic map has any unknown divs, then we can only assume
2692 : * that they do not live in the same local space.
2693 : */
2694 2337474935 : static isl_bool same_divs(__isl_keep isl_basic_map *bmap1,
2695 : __isl_keep isl_basic_map *bmap2)
2696 : {
2697 : int i;
2698 : isl_bool known;
2699 : int total;
2700 :
2701 2337474935 : if (!bmap1 || !bmap2)
2702 0 : return isl_bool_error;
2703 2337474935 : if (bmap1->n_div != bmap2->n_div)
2704 0 : return isl_bool_false;
2705 :
2706 2337474935 : if (bmap1->n_div == 0)
2707 2337474935 : return isl_bool_true;
2708 :
2709 0 : known = isl_basic_map_divs_known(bmap1);
2710 0 : if (known < 0 || !known)
2711 0 : return known;
2712 0 : known = isl_basic_map_divs_known(bmap2);
2713 0 : if (known < 0 || !known)
2714 0 : return known;
2715 :
2716 0 : total = isl_basic_map_total_dim(bmap1);
2717 0 : for (i = 0; i < bmap1->n_div; ++i)
2718 0 : if (!isl_seq_eq(bmap1->div[i], bmap2->div[i], 2 + total))
2719 0 : return isl_bool_false;
2720 :
2721 0 : return isl_bool_true;
2722 : }
2723 :
2724 : /* Assuming that "tab" contains the equality constraints and
2725 : * the initial inequality constraints of "bmap", copy the remaining
2726 : * inequality constraints of "bmap" to "Tab".
2727 : */
2728 0 : static isl_stat copy_ineq(struct isl_tab *tab, __isl_keep isl_basic_map *bmap)
2729 : {
2730 : int i, n_ineq;
2731 :
2732 0 : if (!bmap)
2733 0 : return isl_stat_error;
2734 :
2735 0 : n_ineq = tab->n_con - tab->n_eq;
2736 0 : for (i = n_ineq; i < bmap->n_ineq; ++i)
2737 0 : if (isl_tab_add_ineq(tab, bmap->ineq[i]) < 0)
2738 0 : return isl_stat_error;
2739 :
2740 0 : return isl_stat_ok;
2741 : }
2742 :
2743 : /* Description of an integer division that is added
2744 : * during an expansion.
2745 : * "pos" is the position of the corresponding variable.
2746 : * "cst" indicates whether this integer division has a fixed value.
2747 : * "val" contains the fixed value, if the value is fixed.
2748 : */
2749 : struct isl_expanded {
2750 : int pos;
2751 : isl_bool cst;
2752 : isl_int val;
2753 : };
2754 :
2755 : /* For each of the "n" integer division variables "expanded",
2756 : * if the variable has a fixed value, then add two inequality
2757 : * constraints expressing the fixed value.
2758 : * Otherwise, add the corresponding div constraints.
2759 : * The caller is responsible for removing the div constraints
2760 : * that it added for all these "n" integer divisions.
2761 : *
2762 : * The div constraints and the pair of inequality constraints
2763 : * forcing the fixed value cannot both be added for a given variable
2764 : * as the combination may render some of the original constraints redundant.
2765 : * These would then be ignored during the coalescing detection,
2766 : * while they could remain in the fused result.
2767 : *
2768 : * The two added inequality constraints are
2769 : *
2770 : * -a + v >= 0
2771 : * a - v >= 0
2772 : *
2773 : * with "a" the variable and "v" its fixed value.
2774 : * The facet corresponding to one of these two constraints is selected
2775 : * in the tableau to ensure that the pair of inequality constraints
2776 : * is treated as an equality constraint.
2777 : *
2778 : * The information in info->ineq is thrown away because it was
2779 : * computed in terms of div constraints, while some of those
2780 : * have now been replaced by these pairs of inequality constraints.
2781 : */
2782 0 : static isl_stat fix_constant_divs(struct isl_coalesce_info *info,
2783 : int n, struct isl_expanded *expanded)
2784 : {
2785 : unsigned o_div;
2786 : int i;
2787 : isl_vec *ineq;
2788 :
2789 0 : o_div = isl_basic_map_offset(info->bmap, isl_dim_div) - 1;
2790 0 : ineq = isl_vec_alloc(isl_tab_get_ctx(info->tab), 1 + info->tab->n_var);
2791 0 : if (!ineq)
2792 0 : return isl_stat_error;
2793 0 : isl_seq_clr(ineq->el + 1, info->tab->n_var);
2794 :
2795 0 : for (i = 0; i < n; ++i) {
2796 0 : if (!expanded[i].cst) {
2797 0 : info->bmap = isl_basic_map_extend_constraints(
2798 : info->bmap, 0, 2);
2799 0 : if (isl_basic_map_add_div_constraints(info->bmap,
2800 0 : expanded[i].pos - o_div) < 0)
2801 0 : break;
2802 : } else {
2803 0 : isl_int_set_si(ineq->el[1 + expanded[i].pos], -1);
2804 0 : isl_int_set(ineq->el[0], expanded[i].val);
2805 0 : info->bmap = isl_basic_map_add_ineq(info->bmap,
2806 : ineq->el);
2807 0 : isl_int_set_si(ineq->el[1 + expanded[i].pos], 1);
2808 0 : isl_int_neg(ineq->el[0], expanded[i].val);
2809 0 : info->bmap = isl_basic_map_add_ineq(info->bmap,
2810 : ineq->el);
2811 0 : isl_int_set_si(ineq->el[1 + expanded[i].pos], 0);
2812 : }
2813 0 : if (copy_ineq(info->tab, info->bmap) < 0)
2814 0 : break;
2815 0 : if (expanded[i].cst &&
2816 0 : isl_tab_select_facet(info->tab, info->tab->n_con - 1) < 0)
2817 0 : break;
2818 : }
2819 :
2820 0 : isl_vec_free(ineq);
2821 :
2822 0 : clear_status(info);
2823 0 : init_status(info);
2824 :
2825 0 : return i < n ? isl_stat_error : isl_stat_ok;
2826 : }
2827 :
2828 : /* Insert the "n" integer division variables "expanded"
2829 : * into info->tab and info->bmap and
2830 : * update info->ineq with respect to the redundant constraints
2831 : * in the resulting tableau.
2832 : * "bmap" contains the result of this insertion in info->bmap,
2833 : * while info->bmap is the original version
2834 : * of "bmap", i.e., the one that corresponds to the current
2835 : * state of info->tab. The number of constraints in info->bmap
2836 : * is assumed to be the same as the number of constraints
2837 : * in info->tab. This is required to be able to detect
2838 : * the extra constraints in "bmap".
2839 : *
2840 : * In particular, introduce extra variables corresponding
2841 : * to the extra integer divisions and add the div constraints
2842 : * that were added to "bmap" after info->tab was created
2843 : * from info->bmap.
2844 : * Furthermore, check if these extra integer divisions happen
2845 : * to attain a fixed integer value in info->tab.
2846 : * If so, replace the corresponding div constraints by pairs
2847 : * of inequality constraints that fix these
2848 : * integer divisions to their single integer values.
2849 : * Replace info->bmap by "bmap" to match the changes to info->tab.
2850 : * info->ineq was computed without a tableau and therefore
2851 : * does not take into account the redundant constraints
2852 : * in the tableau. Mark them here.
2853 : * There is no need to check the newly added div constraints
2854 : * since they cannot be redundant.
2855 : * The redundancy check is not performed when constants have been discovered
2856 : * since info->ineq is completely thrown away in this case.
2857 : */
2858 0 : static isl_stat tab_insert_divs(struct isl_coalesce_info *info,
2859 : int n, struct isl_expanded *expanded, __isl_take isl_basic_map *bmap)
2860 : {
2861 : int i, n_ineq;
2862 : unsigned n_eq;
2863 : struct isl_tab_undo *snap;
2864 : int any;
2865 :
2866 0 : if (!bmap)
2867 0 : return isl_stat_error;
2868 0 : if (info->bmap->n_eq + info->bmap->n_ineq != info->tab->n_con)
2869 0 : isl_die(isl_basic_map_get_ctx(bmap), isl_error_internal,
2870 : "original tableau does not correspond "
2871 : "to original basic map", goto error);
2872 :
2873 0 : if (isl_tab_extend_vars(info->tab, n) < 0)
2874 0 : goto error;
2875 0 : if (isl_tab_extend_cons(info->tab, 2 * n) < 0)
2876 0 : goto error;
2877 :
2878 0 : for (i = 0; i < n; ++i) {
2879 0 : if (isl_tab_insert_var(info->tab, expanded[i].pos) < 0)
2880 0 : goto error;
2881 : }
2882 :
2883 0 : snap = isl_tab_snap(info->tab);
2884 :
2885 0 : n_ineq = info->tab->n_con - info->tab->n_eq;
2886 0 : if (copy_ineq(info->tab, bmap) < 0)
2887 0 : goto error;
2888 :
2889 0 : isl_basic_map_free(info->bmap);
2890 0 : info->bmap = bmap;
2891 :
2892 0 : any = 0;
2893 0 : for (i = 0; i < n; ++i) {
2894 0 : expanded[i].cst = isl_tab_is_constant(info->tab,
2895 0 : expanded[i].pos, &expanded[i].val);
2896 0 : if (expanded[i].cst < 0)
2897 0 : return isl_stat_error;
2898 0 : if (expanded[i].cst)
2899 0 : any = 1;
2900 : }
2901 :
2902 0 : if (any) {
2903 0 : if (isl_tab_rollback(info->tab, snap) < 0)
2904 0 : return isl_stat_error;
2905 0 : info->bmap = isl_basic_map_cow(info->bmap);
2906 0 : if (isl_basic_map_free_inequality(info->bmap, 2 * n) < 0)
2907 0 : return isl_stat_error;
2908 :
2909 0 : return fix_constant_divs(info, n, expanded);
2910 : }
2911 :
2912 0 : n_eq = info->bmap->n_eq;
2913 0 : for (i = 0; i < n_ineq; ++i) {
2914 0 : if (isl_tab_is_redundant(info->tab, n_eq + i))
2915 0 : info->ineq[i] = STATUS_REDUNDANT;
2916 : }
2917 :
2918 0 : return isl_stat_ok;
2919 : error:
2920 0 : isl_basic_map_free(bmap);
2921 0 : return isl_stat_error;
2922 : }
2923 :
2924 : /* Expand info->tab and info->bmap in the same way "bmap" was expanded
2925 : * in isl_basic_map_expand_divs using the expansion "exp" and
2926 : * update info->ineq with respect to the redundant constraints
2927 : * in the resulting tableau. info->bmap is the original version
2928 : * of "bmap", i.e., the one that corresponds to the current
2929 : * state of info->tab. The number of constraints in info->bmap
2930 : * is assumed to be the same as the number of constraints
2931 : * in info->tab. This is required to be able to detect
2932 : * the extra constraints in "bmap".
2933 : *
2934 : * Extract the positions where extra local variables are introduced
2935 : * from "exp" and call tab_insert_divs.
2936 : */
2937 0 : static isl_stat expand_tab(struct isl_coalesce_info *info, int *exp,
2938 : __isl_take isl_basic_map *bmap)
2939 : {
2940 : isl_ctx *ctx;
2941 : struct isl_expanded *expanded;
2942 : int i, j, k, n;
2943 : int extra_var;
2944 : unsigned total, pos, n_div;
2945 : isl_stat r;
2946 :
2947 0 : total = isl_basic_map_dim(bmap, isl_dim_all);
2948 0 : n_div = isl_basic_map_dim(bmap, isl_dim_div);
2949 0 : pos = total - n_div;
2950 0 : extra_var = total - info->tab->n_var;
2951 0 : n = n_div - extra_var;
2952 :
2953 0 : ctx = isl_basic_map_get_ctx(bmap);
2954 0 : expanded = isl_calloc_array(ctx, struct isl_expanded, extra_var);
2955 0 : if (extra_var && !expanded)
2956 0 : goto error;
2957 :
2958 0 : i = 0;
2959 0 : k = 0;
2960 0 : for (j = 0; j < n_div; ++j) {
2961 0 : if (i < n && exp[i] == j) {
2962 0 : ++i;
2963 0 : continue;
2964 : }
2965 0 : expanded[k++].pos = pos + j;
2966 : }
2967 :
2968 0 : for (k = 0; k < extra_var; ++k)
2969 0 : isl_int_init(expanded[k].val);
2970 :
2971 0 : r = tab_insert_divs(info, extra_var, expanded, bmap);
2972 :
2973 0 : for (k = 0; k < extra_var; ++k)
2974 0 : isl_int_clear(expanded[k].val);
2975 0 : free(expanded);
2976 :
2977 0 : return r;
2978 : error:
2979 0 : isl_basic_map_free(bmap);
2980 0 : return isl_stat_error;
2981 : }
2982 :
2983 : /* Check if the union of the basic maps represented by info[i] and info[j]
2984 : * can be represented by a single basic map,
2985 : * after expanding the divs of info[i] to match those of info[j].
2986 : * If so, replace the pair by the single basic map and return
2987 : * isl_change_drop_first, isl_change_drop_second or isl_change_fuse.
2988 : * Otherwise, return isl_change_none.
2989 : *
2990 : * The caller has already checked for info[j] being a subset of info[i].
2991 : * If some of the divs of info[j] are unknown, then the expanded info[i]
2992 : * will not have the corresponding div constraints. The other patterns
2993 : * therefore cannot apply. Skip the computation in this case.
2994 : *
2995 : * The expansion is performed using the divs "div" and expansion "exp"
2996 : * computed by the caller.
2997 : * info[i].bmap has already been expanded and the result is passed in
2998 : * as "bmap".
2999 : * The "eq" and "ineq" fields of info[i] reflect the status of
3000 : * the constraints of the expanded "bmap" with respect to info[j].tab.
3001 : * However, inequality constraints that are redundant in info[i].tab
3002 : * have not yet been marked as such because no tableau was available.
3003 : *
3004 : * Replace info[i].bmap by "bmap" and expand info[i].tab as well,
3005 : * updating info[i].ineq with respect to the redundant constraints.
3006 : * Then try and coalesce the expanded info[i] with info[j],
3007 : * reusing the information in info[i].eq and info[i].ineq.
3008 : * If this does not result in any coalescing or if it results in info[j]
3009 : * getting dropped (which should not happen in practice, since the case
3010 : * of info[j] being a subset of info[i] has already been checked by
3011 : * the caller), then revert info[i] to its original state.
3012 : */
3013 0 : static enum isl_change coalesce_expand_tab_divs(__isl_take isl_basic_map *bmap,
3014 : int i, int j, struct isl_coalesce_info *info, __isl_keep isl_mat *div,
3015 : int *exp)
3016 : {
3017 : isl_bool known;
3018 : isl_basic_map *bmap_i;
3019 : struct isl_tab_undo *snap;
3020 0 : enum isl_change change = isl_change_none;
3021 :
3022 0 : known = isl_basic_map_divs_known(info[j].bmap);
3023 0 : if (known < 0 || !known) {
3024 0 : clear_status(&info[i]);
3025 0 : isl_basic_map_free(bmap);
3026 0 : return known < 0 ? isl_change_error : isl_change_none;
3027 : }
3028 :
3029 0 : bmap_i = isl_basic_map_copy(info[i].bmap);
3030 0 : snap = isl_tab_snap(info[i].tab);
3031 0 : if (expand_tab(&info[i], exp, bmap) < 0)
3032 0 : change = isl_change_error;
3033 :
3034 0 : init_status(&info[j]);
3035 0 : if (change == isl_change_none)
3036 0 : change = coalesce_local_pair_reuse(i, j, info);
3037 : else
3038 0 : clear_status(&info[i]);
3039 0 : if (change != isl_change_none && change != isl_change_drop_second) {
3040 0 : isl_basic_map_free(bmap_i);
3041 : } else {
3042 0 : isl_basic_map_free(info[i].bmap);
3043 0 : info[i].bmap = bmap_i;
3044 :
3045 0 : if (isl_tab_rollback(info[i].tab, snap) < 0)
3046 0 : change = isl_change_error;
3047 : }
3048 :
3049 0 : return change;
3050 : }
3051 :
3052 : /* Check if the union of "bmap" and the basic map represented by info[j]
3053 : * can be represented by a single basic map,
3054 : * after expanding the divs of "bmap" to match those of info[j].
3055 : * If so, replace the pair by the single basic map and return
3056 : * isl_change_drop_first, isl_change_drop_second or isl_change_fuse.
3057 : * Otherwise, return isl_change_none.
3058 : *
3059 : * In particular, check if the expanded "bmap" contains the basic map
3060 : * represented by the tableau info[j].tab.
3061 : * The expansion is performed using the divs "div" and expansion "exp"
3062 : * computed by the caller.
3063 : * Then we check if all constraints of the expanded "bmap" are valid for
3064 : * info[j].tab.
3065 : *
3066 : * If "i" is not equal to -1, then "bmap" is equal to info[i].bmap.
3067 : * In this case, the positions of the constraints of info[i].bmap
3068 : * with respect to the basic map represented by info[j] are stored
3069 : * in info[i].
3070 : *
3071 : * If the expanded "bmap" does not contain the basic map
3072 : * represented by the tableau info[j].tab and if "i" is not -1,
3073 : * i.e., if the original "bmap" is info[i].bmap, then expand info[i].tab
3074 : * as well and check if that results in coalescing.
3075 : */
3076 0 : static enum isl_change coalesce_with_expanded_divs(
3077 : __isl_keep isl_basic_map *bmap, int i, int j,
3078 : struct isl_coalesce_info *info, __isl_keep isl_mat *div, int *exp)
3079 : {
3080 0 : enum isl_change change = isl_change_none;
3081 : struct isl_coalesce_info info_local, *info_i;
3082 :
3083 0 : info_i = i >= 0 ? &info[i] : &info_local;
3084 0 : init_status(info_i);
3085 0 : bmap = isl_basic_map_copy(bmap);
3086 0 : bmap = isl_basic_map_expand_divs(bmap, isl_mat_copy(div), exp);
3087 0 : bmap = isl_basic_map_mark_final(bmap);
3088 :
3089 0 : if (!bmap)
3090 0 : goto error;
3091 :
3092 0 : info_local.bmap = bmap;
3093 0 : info_i->eq = eq_status_in(bmap, info[j].tab);
3094 0 : if (bmap->n_eq && !info_i->eq)
3095 0 : goto error;
3096 0 : if (any_eq(info_i, STATUS_ERROR))
3097 0 : goto error;
3098 0 : if (any_eq(info_i, STATUS_SEPARATE))
3099 0 : goto done;
3100 :
3101 0 : info_i->ineq = ineq_status_in(bmap, NULL, info[j].tab);
3102 0 : if (bmap->n_ineq && !info_i->ineq)
3103 0 : goto error;
3104 0 : if (any_ineq(info_i, STATUS_ERROR))
3105 0 : goto error;
3106 0 : if (any_ineq(info_i, STATUS_SEPARATE))
3107 0 : goto done;
3108 :
3109 0 : if (all(info_i->eq, 2 * bmap->n_eq, STATUS_VALID) &&
3110 0 : all(info_i->ineq, bmap->n_ineq, STATUS_VALID)) {
3111 0 : drop(&info[j]);
3112 0 : change = isl_change_drop_second;
3113 : }
3114 :
3115 0 : if (change == isl_change_none && i != -1)
3116 0 : return coalesce_expand_tab_divs(bmap, i, j, info, div, exp);
3117 :
3118 : done:
3119 0 : isl_basic_map_free(bmap);
3120 0 : clear_status(info_i);
3121 0 : return change;
3122 : error:
3123 0 : isl_basic_map_free(bmap);
3124 0 : clear_status(info_i);
3125 0 : return isl_change_error;
3126 : }
3127 :
3128 : /* Check if the union of "bmap_i" and the basic map represented by info[j]
3129 : * can be represented by a single basic map,
3130 : * after aligning the divs of "bmap_i" to match those of info[j].
3131 : * If so, replace the pair by the single basic map and return
3132 : * isl_change_drop_first, isl_change_drop_second or isl_change_fuse.
3133 : * Otherwise, return isl_change_none.
3134 : *
3135 : * In particular, check if "bmap_i" contains the basic map represented by
3136 : * info[j] after aligning the divs of "bmap_i" to those of info[j].
3137 : * Note that this can only succeed if the number of divs of "bmap_i"
3138 : * is smaller than (or equal to) the number of divs of info[j].
3139 : *
3140 : * We first check if the divs of "bmap_i" are all known and form a subset
3141 : * of those of info[j].bmap. If so, we pass control over to
3142 : * coalesce_with_expanded_divs.
3143 : *
3144 : * If "i" is not equal to -1, then "bmap" is equal to info[i].bmap.
3145 : */
3146 0 : static enum isl_change coalesce_after_aligning_divs(
3147 : __isl_keep isl_basic_map *bmap_i, int i, int j,
3148 : struct isl_coalesce_info *info)
3149 : {
3150 : isl_bool known;
3151 : isl_mat *div_i, *div_j, *div;
3152 0 : int *exp1 = NULL;
3153 0 : int *exp2 = NULL;
3154 : isl_ctx *ctx;
3155 : enum isl_change change;
3156 :
3157 0 : known = isl_basic_map_divs_known(bmap_i);
3158 0 : if (known < 0)
3159 0 : return isl_change_error;
3160 0 : if (!known)
3161 0 : return isl_change_none;
3162 :
3163 0 : ctx = isl_basic_map_get_ctx(bmap_i);
3164 :
3165 0 : div_i = isl_basic_map_get_divs(bmap_i);
3166 0 : div_j = isl_basic_map_get_divs(info[j].bmap);
3167 :
3168 0 : if (!div_i || !div_j)
3169 : goto error;
3170 :
3171 0 : exp1 = isl_alloc_array(ctx, int, div_i->n_row);
3172 0 : exp2 = isl_alloc_array(ctx, int, div_j->n_row);
3173 0 : if ((div_i->n_row && !exp1) || (div_j->n_row && !exp2))
3174 : goto error;
3175 :
3176 0 : div = isl_merge_divs(div_i, div_j, exp1, exp2);
3177 0 : if (!div)
3178 0 : goto error;
3179 :
3180 0 : if (div->n_row == div_j->n_row)
3181 0 : change = coalesce_with_expanded_divs(bmap_i,
3182 : i, j, info, div, exp1);
3183 : else
3184 0 : change = isl_change_none;
3185 :
3186 0 : isl_mat_free(div);
3187 :
3188 0 : isl_mat_free(div_i);
3189 0 : isl_mat_free(div_j);
3190 :
3191 0 : free(exp2);
3192 0 : free(exp1);
3193 :
3194 0 : return change;
3195 : error:
3196 0 : isl_mat_free(div_i);
3197 0 : isl_mat_free(div_j);
3198 0 : free(exp1);
3199 0 : free(exp2);
3200 0 : return isl_change_error;
3201 : }
3202 :
3203 : /* Check if basic map "j" is a subset of basic map "i" after
3204 : * exploiting the extra equalities of "j" to simplify the divs of "i".
3205 : * If so, remove basic map "j" and return isl_change_drop_second.
3206 : *
3207 : * If "j" does not have any equalities or if they are the same
3208 : * as those of "i", then we cannot exploit them to simplify the divs.
3209 : * Similarly, if there are no divs in "i", then they cannot be simplified.
3210 : * If, on the other hand, the affine hulls of "i" and "j" do not intersect,
3211 : * then "j" cannot be a subset of "i".
3212 : *
3213 : * Otherwise, we intersect "i" with the affine hull of "j" and then
3214 : * check if "j" is a subset of the result after aligning the divs.
3215 : * If so, then "j" is definitely a subset of "i" and can be removed.
3216 : * Note that if after intersection with the affine hull of "j".
3217 : * "i" still has more divs than "j", then there is no way we can
3218 : * align the divs of "i" to those of "j".
3219 : */
3220 0 : static enum isl_change coalesce_subset_with_equalities(int i, int j,
3221 : struct isl_coalesce_info *info)
3222 : {
3223 : isl_basic_map *hull_i, *hull_j, *bmap_i;
3224 : int equal, empty;
3225 : enum isl_change change;
3226 :
3227 0 : if (info[j].bmap->n_eq == 0)
3228 0 : return isl_change_none;
3229 0 : if (info[i].bmap->n_div == 0)
3230 0 : return isl_change_none;
3231 :
3232 0 : hull_i = isl_basic_map_copy(info[i].bmap);
3233 0 : hull_i = isl_basic_map_plain_affine_hull(hull_i);
3234 0 : hull_j = isl_basic_map_copy(info[j].bmap);
3235 0 : hull_j = isl_basic_map_plain_affine_hull(hull_j);
3236 :
3237 0 : hull_j = isl_basic_map_intersect(hull_j, isl_basic_map_copy(hull_i));
3238 0 : equal = isl_basic_map_plain_is_equal(hull_i, hull_j);
3239 0 : empty = isl_basic_map_plain_is_empty(hull_j);
3240 0 : isl_basic_map_free(hull_i);
3241 :
3242 0 : if (equal < 0 || equal || empty < 0 || empty) {
3243 0 : isl_basic_map_free(hull_j);
3244 0 : if (equal < 0 || empty < 0)
3245 0 : return isl_change_error;
3246 0 : return isl_change_none;
3247 : }
3248 :
3249 0 : bmap_i = isl_basic_map_copy(info[i].bmap);
3250 0 : bmap_i = isl_basic_map_intersect(bmap_i, hull_j);
3251 0 : if (!bmap_i)
3252 0 : return isl_change_error;
3253 :
3254 0 : if (bmap_i->n_div > info[j].bmap->n_div) {
3255 0 : isl_basic_map_free(bmap_i);
3256 0 : return isl_change_none;
3257 : }
3258 :
3259 0 : change = coalesce_after_aligning_divs(bmap_i, -1, j, info);
3260 :
3261 0 : isl_basic_map_free(bmap_i);
3262 :
3263 0 : return change;
3264 : }
3265 :
3266 : /* Check if the union of and the basic maps represented by info[i] and info[j]
3267 : * can be represented by a single basic map, by aligning or equating
3268 : * their integer divisions.
3269 : * If so, replace the pair by the single basic map and return
3270 : * isl_change_drop_first, isl_change_drop_second or isl_change_fuse.
3271 : * Otherwise, return isl_change_none.
3272 : *
3273 : * Note that we only perform any test if the number of divs is different
3274 : * in the two basic maps. In case the number of divs is the same,
3275 : * we have already established that the divs are different
3276 : * in the two basic maps.
3277 : * In particular, if the number of divs of basic map i is smaller than
3278 : * the number of divs of basic map j, then we check if j is a subset of i
3279 : * and vice versa.
3280 : */
3281 0 : static enum isl_change coalesce_divs(int i, int j,
3282 : struct isl_coalesce_info *info)
3283 : {
3284 0 : enum isl_change change = isl_change_none;
3285 :
3286 0 : if (info[i].bmap->n_div < info[j].bmap->n_div)
3287 0 : change = coalesce_after_aligning_divs(info[i].bmap, i, j, info);
3288 0 : if (change != isl_change_none)
3289 0 : return change;
3290 :
3291 0 : if (info[j].bmap->n_div < info[i].bmap->n_div)
3292 0 : change = coalesce_after_aligning_divs(info[j].bmap, j, i, info);
3293 0 : if (change != isl_change_none)
3294 0 : return invert_change(change);
3295 :
3296 0 : change = coalesce_subset_with_equalities(i, j, info);
3297 0 : if (change != isl_change_none)
3298 0 : return change;
3299 :
3300 0 : change = coalesce_subset_with_equalities(j, i, info);
3301 0 : if (change != isl_change_none)
3302 0 : return invert_change(change);
3303 :
3304 0 : return isl_change_none;
3305 : }
3306 :
3307 : /* Does "bmap" involve any divs that themselves refer to divs?
3308 : */
3309 0 : static isl_bool has_nested_div(__isl_keep isl_basic_map *bmap)
3310 : {
3311 : int i;
3312 : unsigned total;
3313 : unsigned n_div;
3314 :
3315 0 : total = isl_basic_map_dim(bmap, isl_dim_all);
3316 0 : n_div = isl_basic_map_dim(bmap, isl_dim_div);
3317 0 : total -= n_div;
3318 :
3319 0 : for (i = 0; i < n_div; ++i)
3320 0 : if (isl_seq_first_non_zero(bmap->div[i] + 2 + total,
3321 : n_div) != -1)
3322 0 : return isl_bool_true;
3323 :
3324 0 : return isl_bool_false;
3325 : }
3326 :
3327 : /* Return a list of affine expressions, one for each integer division
3328 : * in "bmap_i". For each integer division that also appears in "bmap_j",
3329 : * the affine expression is set to NaN. The number of NaNs in the list
3330 : * is equal to the number of integer divisions in "bmap_j".
3331 : * For the other integer divisions of "bmap_i", the corresponding
3332 : * element in the list is a purely affine expression equal to the integer
3333 : * division in "hull".
3334 : * If no such list can be constructed, then the number of elements
3335 : * in the returned list is smaller than the number of integer divisions
3336 : * in "bmap_i".
3337 : */
3338 0 : static __isl_give isl_aff_list *set_up_substitutions(
3339 : __isl_keep isl_basic_map *bmap_i, __isl_keep isl_basic_map *bmap_j,
3340 : __isl_take isl_basic_map *hull)
3341 : {
3342 : unsigned n_div_i, n_div_j, total;
3343 : isl_ctx *ctx;
3344 : isl_local_space *ls;
3345 : isl_basic_set *wrap_hull;
3346 : isl_aff *aff_nan;
3347 : isl_aff_list *list;
3348 : int i, j;
3349 :
3350 0 : if (!hull)
3351 0 : return NULL;
3352 :
3353 0 : ctx = isl_basic_map_get_ctx(hull);
3354 :
3355 0 : n_div_i = isl_basic_map_dim(bmap_i, isl_dim_div);
3356 0 : n_div_j = isl_basic_map_dim(bmap_j, isl_dim_div);
3357 0 : total = isl_basic_map_total_dim(bmap_i) - n_div_i;
3358 :
3359 0 : ls = isl_basic_map_get_local_space(bmap_i);
3360 0 : ls = isl_local_space_wrap(ls);
3361 0 : wrap_hull = isl_basic_map_wrap(hull);
3362 :
3363 0 : aff_nan = isl_aff_nan_on_domain(isl_local_space_copy(ls));
3364 0 : list = isl_aff_list_alloc(ctx, n_div_i);
3365 :
3366 0 : j = 0;
3367 0 : for (i = 0; i < n_div_i; ++i) {
3368 : isl_aff *aff;
3369 :
3370 0 : if (j < n_div_j &&
3371 0 : isl_basic_map_equal_div_expr_part(bmap_i, i, bmap_j, j,
3372 : 0, 2 + total)) {
3373 0 : ++j;
3374 0 : list = isl_aff_list_add(list, isl_aff_copy(aff_nan));
3375 0 : continue;
3376 : }
3377 0 : if (n_div_i - i <= n_div_j - j)
3378 0 : break;
3379 :
3380 0 : aff = isl_local_space_get_div(ls, i);
3381 0 : aff = isl_aff_substitute_equalities(aff,
3382 : isl_basic_set_copy(wrap_hull));
3383 0 : aff = isl_aff_floor(aff);
3384 0 : if (!aff)
3385 0 : goto error;
3386 0 : if (isl_aff_dim(aff, isl_dim_div) != 0) {
3387 0 : isl_aff_free(aff);
3388 0 : break;
3389 : }
3390 :
3391 0 : list = isl_aff_list_add(list, aff);
3392 : }
3393 :
3394 0 : isl_aff_free(aff_nan);
3395 0 : isl_local_space_free(ls);
3396 0 : isl_basic_set_free(wrap_hull);
3397 :
3398 0 : return list;
3399 : error:
3400 0 : isl_aff_free(aff_nan);
3401 0 : isl_local_space_free(ls);
3402 0 : isl_basic_set_free(wrap_hull);
3403 0 : isl_aff_list_free(list);
3404 0 : return NULL;
3405 : }
3406 :
3407 : /* Add variables to info->bmap and info->tab corresponding to the elements
3408 : * in "list" that are not set to NaN.
3409 : * "extra_var" is the number of these elements.
3410 : * "dim" is the offset in the variables of "tab" where we should
3411 : * start considering the elements in "list".
3412 : * When this function returns, the total number of variables in "tab"
3413 : * is equal to "dim" plus the number of elements in "list".
3414 : *
3415 : * The newly added existentially quantified variables are not given
3416 : * an explicit representation because the corresponding div constraints
3417 : * do not appear in info->bmap. These constraints are not added
3418 : * to info->bmap because for internal consistency, they would need to
3419 : * be added to info->tab as well, where they could combine with the equality
3420 : * that is added later to result in constraints that do not hold
3421 : * in the original input.
3422 : */
3423 0 : static isl_stat add_sub_vars(struct isl_coalesce_info *info,
3424 : __isl_keep isl_aff_list *list, int dim, int extra_var)
3425 : {
3426 : int i, j, n, d;
3427 : isl_space *space;
3428 :
3429 0 : space = isl_basic_map_get_space(info->bmap);
3430 0 : info->bmap = isl_basic_map_cow(info->bmap);
3431 0 : info->bmap = isl_basic_map_extend_space(info->bmap, space,
3432 : extra_var, 0, 0);
3433 0 : if (!info->bmap)
3434 0 : return isl_stat_error;
3435 0 : n = isl_aff_list_n_aff(list);
3436 0 : for (i = 0; i < n; ++i) {
3437 : int is_nan;
3438 : isl_aff *aff;
3439 :
3440 0 : aff = isl_aff_list_get_aff(list, i);
3441 0 : is_nan = isl_aff_is_nan(aff);
3442 0 : isl_aff_free(aff);
3443 0 : if (is_nan < 0)
3444 0 : return isl_stat_error;
3445 0 : if (is_nan)
3446 0 : continue;
3447 :
3448 0 : if (isl_tab_insert_var(info->tab, dim + i) < 0)
3449 0 : return isl_stat_error;
3450 0 : d = isl_basic_map_alloc_div(info->bmap);
3451 0 : if (d < 0)
3452 0 : return isl_stat_error;
3453 0 : info->bmap = isl_basic_map_mark_div_unknown(info->bmap, d);
3454 0 : if (!info->bmap)
3455 0 : return isl_stat_error;
3456 0 : for (j = d; j > i; --j)
3457 0 : isl_basic_map_swap_div(info->bmap, j - 1, j);
3458 : }
3459 :
3460 0 : return isl_stat_ok;
3461 : }
3462 :
3463 : /* For each element in "list" that is not set to NaN, fix the corresponding
3464 : * variable in "tab" to the purely affine expression defined by the element.
3465 : * "dim" is the offset in the variables of "tab" where we should
3466 : * start considering the elements in "list".
3467 : *
3468 : * This function assumes that a sufficient number of rows and
3469 : * elements in the constraint array are available in the tableau.
3470 : */
3471 0 : static int add_sub_equalities(struct isl_tab *tab,
3472 : __isl_keep isl_aff_list *list, int dim)
3473 : {
3474 : int i, n;
3475 : isl_ctx *ctx;
3476 : isl_vec *sub;
3477 : isl_aff *aff;
3478 :
3479 0 : n = isl_aff_list_n_aff(list);
3480 :
3481 0 : ctx = isl_tab_get_ctx(tab);
3482 0 : sub = isl_vec_alloc(ctx, 1 + dim + n);
3483 0 : if (!sub)
3484 0 : return -1;
3485 0 : isl_seq_clr(sub->el + 1 + dim, n);
3486 :
3487 0 : for (i = 0; i < n; ++i) {
3488 0 : aff = isl_aff_list_get_aff(list, i);
3489 0 : if (!aff)
3490 0 : goto error;
3491 0 : if (isl_aff_is_nan(aff)) {
3492 0 : isl_aff_free(aff);
3493 0 : continue;
3494 : }
3495 0 : isl_seq_cpy(sub->el, aff->v->el + 1, 1 + dim);
3496 0 : isl_int_neg(sub->el[1 + dim + i], aff->v->el[0]);
3497 0 : if (isl_tab_add_eq(tab, sub->el) < 0)
3498 0 : goto error;
3499 0 : isl_int_set_si(sub->el[1 + dim + i], 0);
3500 0 : isl_aff_free(aff);
3501 : }
3502 :
3503 0 : isl_vec_free(sub);
3504 0 : return 0;
3505 : error:
3506 0 : isl_aff_free(aff);
3507 0 : isl_vec_free(sub);
3508 0 : return -1;
3509 : }
3510 :
3511 : /* Add variables to info->tab and info->bmap corresponding to the elements
3512 : * in "list" that are not set to NaN. The value of the added variable
3513 : * in info->tab is fixed to the purely affine expression defined by the element.
3514 : * "dim" is the offset in the variables of info->tab where we should
3515 : * start considering the elements in "list".
3516 : * When this function returns, the total number of variables in info->tab
3517 : * is equal to "dim" plus the number of elements in "list".
3518 : */
3519 0 : static int add_subs(struct isl_coalesce_info *info,
3520 : __isl_keep isl_aff_list *list, int dim)
3521 : {
3522 : int extra_var;
3523 : int n;
3524 :
3525 0 : if (!list)
3526 0 : return -1;
3527 :
3528 0 : n = isl_aff_list_n_aff(list);
3529 0 : extra_var = n - (info->tab->n_var - dim);
3530 :
3531 0 : if (isl_tab_extend_vars(info->tab, extra_var) < 0)
3532 0 : return -1;
3533 0 : if (isl_tab_extend_cons(info->tab, 2 * extra_var) < 0)
3534 0 : return -1;
3535 0 : if (add_sub_vars(info, list, dim, extra_var) < 0)
3536 0 : return -1;
3537 :
3538 0 : return add_sub_equalities(info->tab, list, dim);
3539 : }
3540 :
3541 : /* Coalesce basic map "j" into basic map "i" after adding the extra integer
3542 : * divisions in "i" but not in "j" to basic map "j", with values
3543 : * specified by "list". The total number of elements in "list"
3544 : * is equal to the number of integer divisions in "i", while the number
3545 : * of NaN elements in the list is equal to the number of integer divisions
3546 : * in "j".
3547 : *
3548 : * If no coalescing can be performed, then we need to revert basic map "j"
3549 : * to its original state. We do the same if basic map "i" gets dropped
3550 : * during the coalescing, even though this should not happen in practice
3551 : * since we have already checked for "j" being a subset of "i"
3552 : * before we reach this stage.
3553 : */
3554 0 : static enum isl_change coalesce_with_subs(int i, int j,
3555 : struct isl_coalesce_info *info, __isl_keep isl_aff_list *list)
3556 : {
3557 : isl_basic_map *bmap_j;
3558 : struct isl_tab_undo *snap;
3559 : unsigned dim;
3560 : enum isl_change change;
3561 :
3562 0 : bmap_j = isl_basic_map_copy(info[j].bmap);
3563 0 : snap = isl_tab_snap(info[j].tab);
3564 :
3565 0 : dim = isl_basic_map_dim(bmap_j, isl_dim_all);
3566 0 : dim -= isl_basic_map_dim(bmap_j, isl_dim_div);
3567 0 : if (add_subs(&info[j], list, dim) < 0)
3568 0 : goto error;
3569 :
3570 0 : change = coalesce_local_pair(i, j, info);
3571 0 : if (change != isl_change_none && change != isl_change_drop_first) {
3572 0 : isl_basic_map_free(bmap_j);
3573 : } else {
3574 0 : isl_basic_map_free(info[j].bmap);
3575 0 : info[j].bmap = bmap_j;
3576 :
3577 0 : if (isl_tab_rollback(info[j].tab, snap) < 0)
3578 0 : return isl_change_error;
3579 : }
3580 :
3581 0 : return change;
3582 : error:
3583 0 : isl_basic_map_free(bmap_j);
3584 0 : return isl_change_error;
3585 : }
3586 :
3587 : /* Check if we can coalesce basic map "j" into basic map "i" after copying
3588 : * those extra integer divisions in "i" that can be simplified away
3589 : * using the extra equalities in "j".
3590 : * All divs are assumed to be known and not contain any nested divs.
3591 : *
3592 : * We first check if there are any extra equalities in "j" that we
3593 : * can exploit. Then we check if every integer division in "i"
3594 : * either already appears in "j" or can be simplified using the
3595 : * extra equalities to a purely affine expression.
3596 : * If these tests succeed, then we try to coalesce the two basic maps
3597 : * by introducing extra dimensions in "j" corresponding to
3598 : * the extra integer divsisions "i" fixed to the corresponding
3599 : * purely affine expression.
3600 : */
3601 0 : static enum isl_change check_coalesce_into_eq(int i, int j,
3602 : struct isl_coalesce_info *info)
3603 : {
3604 : unsigned n_div_i, n_div_j;
3605 : isl_basic_map *hull_i, *hull_j;
3606 : int equal, empty;
3607 : isl_aff_list *list;
3608 : enum isl_change change;
3609 :
3610 0 : n_div_i = isl_basic_map_dim(info[i].bmap, isl_dim_div);
3611 0 : n_div_j = isl_basic_map_dim(info[j].bmap, isl_dim_div);
3612 0 : if (n_div_i <= n_div_j)
3613 0 : return isl_change_none;
3614 0 : if (info[j].bmap->n_eq == 0)
3615 0 : return isl_change_none;
3616 :
3617 0 : hull_i = isl_basic_map_copy(info[i].bmap);
3618 0 : hull_i = isl_basic_map_plain_affine_hull(hull_i);
3619 0 : hull_j = isl_basic_map_copy(info[j].bmap);
3620 0 : hull_j = isl_basic_map_plain_affine_hull(hull_j);
3621 :
3622 0 : hull_j = isl_basic_map_intersect(hull_j, isl_basic_map_copy(hull_i));
3623 0 : equal = isl_basic_map_plain_is_equal(hull_i, hull_j);
3624 0 : empty = isl_basic_map_plain_is_empty(hull_j);
3625 0 : isl_basic_map_free(hull_i);
3626 :
3627 0 : if (equal < 0 || empty < 0)
3628 : goto error;
3629 0 : if (equal || empty) {
3630 0 : isl_basic_map_free(hull_j);
3631 0 : return isl_change_none;
3632 : }
3633 :
3634 0 : list = set_up_substitutions(info[i].bmap, info[j].bmap, hull_j);
3635 0 : if (!list)
3636 0 : return isl_change_error;
3637 0 : if (isl_aff_list_n_aff(list) < n_div_i)
3638 0 : change = isl_change_none;
3639 : else
3640 0 : change = coalesce_with_subs(i, j, info, list);
3641 :
3642 0 : isl_aff_list_free(list);
3643 :
3644 0 : return change;
3645 : error:
3646 0 : isl_basic_map_free(hull_j);
3647 0 : return isl_change_error;
3648 : }
3649 :
3650 : /* Check if we can coalesce basic maps "i" and "j" after copying
3651 : * those extra integer divisions in one of the basic maps that can
3652 : * be simplified away using the extra equalities in the other basic map.
3653 : * We require all divs to be known in both basic maps.
3654 : * Furthermore, to simplify the comparison of div expressions,
3655 : * we do not allow any nested integer divisions.
3656 : */
3657 0 : static enum isl_change check_coalesce_eq(int i, int j,
3658 : struct isl_coalesce_info *info)
3659 : {
3660 : isl_bool known, nested;
3661 : enum isl_change change;
3662 :
3663 0 : known = isl_basic_map_divs_known(info[i].bmap);
3664 0 : if (known < 0 || !known)
3665 0 : return known < 0 ? isl_change_error : isl_change_none;
3666 0 : known = isl_basic_map_divs_known(info[j].bmap);
3667 0 : if (known < 0 || !known)
3668 0 : return known < 0 ? isl_change_error : isl_change_none;
3669 0 : nested = has_nested_div(info[i].bmap);
3670 0 : if (nested < 0 || nested)
3671 0 : return nested < 0 ? isl_change_error : isl_change_none;
3672 0 : nested = has_nested_div(info[j].bmap);
3673 0 : if (nested < 0 || nested)
3674 0 : return nested < 0 ? isl_change_error : isl_change_none;
3675 :
3676 0 : change = check_coalesce_into_eq(i, j, info);
3677 0 : if (change != isl_change_none)
3678 0 : return change;
3679 0 : change = check_coalesce_into_eq(j, i, info);
3680 0 : if (change != isl_change_none)
3681 0 : return invert_change(change);
3682 :
3683 0 : return isl_change_none;
3684 : }
3685 :
3686 : /* Check if the union of the given pair of basic maps
3687 : * can be represented by a single basic map.
3688 : * If so, replace the pair by the single basic map and return
3689 : * isl_change_drop_first, isl_change_drop_second or isl_change_fuse.
3690 : * Otherwise, return isl_change_none.
3691 : *
3692 : * We first check if the two basic maps live in the same local space,
3693 : * after aligning the divs that differ by only an integer constant.
3694 : * If so, we do the complete check. Otherwise, we check if they have
3695 : * the same number of integer divisions and can be coalesced, if one is
3696 : * an obvious subset of the other or if the extra integer divisions
3697 : * of one basic map can be simplified away using the extra equalities
3698 : * of the other basic map.
3699 : *
3700 : * Note that trying to coalesce pairs of disjuncts with the same
3701 : * number, but different local variables may drop the explicit
3702 : * representation of some of these local variables.
3703 : * This operation is therefore not performed when
3704 : * the "coalesce_preserve_locals" option is set.
3705 : */
3706 2337474935 : static enum isl_change coalesce_pair(int i, int j,
3707 : struct isl_coalesce_info *info)
3708 : {
3709 : int preserve;
3710 : isl_bool same;
3711 : enum isl_change change;
3712 : isl_ctx *ctx;
3713 :
3714 2337474935 : if (harmonize_divs(&info[i], &info[j]) < 0)
3715 0 : return isl_change_error;
3716 2337474935 : same = same_divs(info[i].bmap, info[j].bmap);
3717 2337474935 : if (same < 0)
3718 0 : return isl_change_error;
3719 2337474935 : if (same)
3720 2337474935 : return coalesce_local_pair(i, j, info);
3721 :
3722 0 : ctx = isl_basic_map_get_ctx(info[i].bmap);
3723 0 : preserve = isl_options_get_coalesce_preserve_locals(ctx);
3724 0 : if (!preserve && info[i].bmap->n_div == info[j].bmap->n_div) {
3725 0 : change = coalesce_local_pair(i, j, info);
3726 0 : if (change != isl_change_none)
3727 0 : return change;
3728 : }
3729 :
3730 0 : change = coalesce_divs(i, j, info);
3731 0 : if (change != isl_change_none)
3732 0 : return change;
3733 :
3734 0 : return check_coalesce_eq(i, j, info);
3735 : }
3736 :
3737 : /* Return the maximum of "a" and "b".
3738 : */
3739 5797558336 : static int isl_max(int a, int b)
3740 : {
3741 5797558336 : return a > b ? a : b;
3742 : }
3743 :
3744 : /* Pairwise coalesce the basic maps in the range [start1, end1[ of "info"
3745 : * with those in the range [start2, end2[, skipping basic maps
3746 : * that have been removed (either before or within this function).
3747 : *
3748 : * For each basic map i in the first range, we check if it can be coalesced
3749 : * with respect to any previously considered basic map j in the second range.
3750 : * If i gets dropped (because it was a subset of some j), then
3751 : * we can move on to the next basic map.
3752 : * If j gets dropped, we need to continue checking against the other
3753 : * previously considered basic maps.
3754 : * If the two basic maps got fused, then we recheck the fused basic map
3755 : * against the previously considered basic maps, starting at i + 1
3756 : * (even if start2 is greater than i + 1).
3757 : */
3758 5797295484 : static int coalesce_range(isl_ctx *ctx, struct isl_coalesce_info *info,
3759 : int start1, int end1, int start2, int end2)
3760 : {
3761 : int i, j;
3762 :
3763 11594961324 : for (i = end1 - 1; i >= start1; --i) {
3764 5797665840 : if (info[i].removed)
3765 107504 : continue;
3766 8136929914 : for (j = isl_max(i + 1, start2); j < end2; ++j) {
3767 : enum isl_change changed;
3768 :
3769 2339371578 : if (info[j].removed)
3770 1896643 : continue;
3771 2337474935 : if (info[i].removed)
3772 0 : isl_die(ctx, isl_error_internal,
3773 : "basic map unexpectedly removed",
3774 : return -1);
3775 2337474935 : changed = coalesce_pair(i, j, info);
3776 2337474935 : switch (changed) {
3777 : case isl_change_error:
3778 0 : return -1;
3779 : case isl_change_none:
3780 : case isl_change_drop_second:
3781 2337383379 : continue;
3782 : case isl_change_drop_first:
3783 9621 : j = end2;
3784 9621 : break;
3785 : case isl_change_fuse:
3786 81935 : j = i;
3787 81935 : break;
3788 : }
3789 : }
3790 : }
3791 :
3792 5797295484 : return 0;
3793 : }
3794 :
3795 : /* Pairwise coalesce the basic maps described by the "n" elements of "info".
3796 : *
3797 : * We consider groups of basic maps that live in the same apparent
3798 : * affine hull and we first coalesce within such a group before we
3799 : * coalesce the elements in the group with elements of previously
3800 : * considered groups. If a fuse happens during the second phase,
3801 : * then we also reconsider the elements within the group.
3802 : */
3803 1208303144 : static int coalesce(isl_ctx *ctx, int n, struct isl_coalesce_info *info)
3804 : {
3805 : int start, end;
3806 :
3807 4106950886 : for (end = n; end > 0; end = start) {
3808 2898647742 : start = end - 1;
3809 7488010438 : while (start >= 1 &&
3810 1690529776 : info[start - 1].hull_hash == info[start].hull_hash)
3811 185178 : start--;
3812 2898647742 : if (coalesce_range(ctx, info, start, end, start, end) < 0)
3813 0 : return -1;
3814 2898647742 : if (coalesce_range(ctx, info, start, end, end, n) < 0)
3815 0 : return -1;
3816 : }
3817 :
3818 1208303144 : return 0;
3819 : }
3820 :
3821 : /* Update the basic maps in "map" based on the information in "info".
3822 : * In particular, remove the basic maps that have been marked removed and
3823 : * update the others based on the information in the corresponding tableau.
3824 : * Since we detected implicit equalities without calling
3825 : * isl_basic_map_gauss, we need to do it now.
3826 : * Also call isl_basic_map_simplify if we may have lost the definition
3827 : * of one or more integer divisions.
3828 : * If a basic map is still equal to the one from which the corresponding "info"
3829 : * entry was created, then redundant constraint and
3830 : * implicit equality constraint detection have been performed
3831 : * on the corresponding tableau and the basic map can be marked as such.
3832 : */
3833 1208303144 : static __isl_give isl_map *update_basic_maps(__isl_take isl_map *map,
3834 : int n, struct isl_coalesce_info *info)
3835 : {
3836 : int i;
3837 :
3838 1208303144 : if (!map)
3839 0 : return NULL;
3840 :
3841 4107136064 : for (i = n - 1; i >= 0; --i) {
3842 2898832920 : if (info[i].removed) {
3843 174894 : isl_basic_map_free(map->p[i]);
3844 174894 : if (i != map->n - 1)
3845 97518 : map->p[i] = map->p[map->n - 1];
3846 174894 : map->n--;
3847 174894 : continue;
3848 : }
3849 :
3850 5797316052 : info[i].bmap = isl_basic_map_update_from_tab(info[i].bmap,
3851 2898658026 : info[i].tab);
3852 2898658026 : info[i].bmap = isl_basic_map_gauss(info[i].bmap, NULL);
3853 2898658026 : if (info[i].simplify)
3854 0 : info[i].bmap = isl_basic_map_simplify(info[i].bmap);
3855 2898658026 : info[i].bmap = isl_basic_map_finalize(info[i].bmap);
3856 2898658026 : if (!info[i].bmap)
3857 0 : return isl_map_free(map);
3858 2898658026 : if (!info[i].modified) {
3859 2898610244 : ISL_F_SET(info[i].bmap, ISL_BASIC_MAP_NO_IMPLICIT);
3860 2898610244 : ISL_F_SET(info[i].bmap, ISL_BASIC_MAP_NO_REDUNDANT);
3861 : }
3862 2898658026 : isl_basic_map_free(map->p[i]);
3863 2898658026 : map->p[i] = info[i].bmap;
3864 2898658026 : info[i].bmap = NULL;
3865 : }
3866 :
3867 1208303144 : return map;
3868 : }
3869 :
3870 : /* For each pair of basic maps in the map, check if the union of the two
3871 : * can be represented by a single basic map.
3872 : * If so, replace the pair by the single basic map and start over.
3873 : *
3874 : * We factor out any (hidden) common factor from the constraint
3875 : * coefficients to improve the detection of adjacent constraints.
3876 : * Note that this function does not call isl_basic_map_gauss,
3877 : * but it does make sure that only a single copy of the basic map
3878 : * is affected. This means that isl_basic_map_gauss may have
3879 : * to be called at the end of the computation (in update_basic_maps)
3880 : * on this single copy to ensure that
3881 : * the basic maps are not left in an unexpected state.
3882 : *
3883 : * Since we are constructing the tableaus of the basic maps anyway,
3884 : * we exploit them to detect implicit equalities and redundant constraints.
3885 : * This also helps the coalescing as it can ignore the redundant constraints.
3886 : * In order to avoid confusion, we make all implicit equalities explicit
3887 : * in the basic maps. If the basic map only has a single reference
3888 : * (this happens in particular if it was modified by
3889 : * isl_basic_map_reduce_coefficients), then isl_basic_map_gauss
3890 : * does not get called on the result. The call to
3891 : * isl_basic_map_gauss in update_basic_maps resolves this as well.
3892 : * For each basic map, we also compute the hash of the apparent affine hull
3893 : * for use in coalesce.
3894 : */
3895 1218389894 : __isl_give isl_map *isl_map_coalesce(__isl_take isl_map *map)
3896 : {
3897 : int i;
3898 : unsigned n;
3899 : isl_ctx *ctx;
3900 1218389894 : struct isl_coalesce_info *info = NULL;
3901 :
3902 1218389894 : map = isl_map_remove_empty_parts(map);
3903 1218389894 : if (!map)
3904 0 : return NULL;
3905 :
3906 1218389894 : if (map->n <= 1)
3907 10086750 : return map;
3908 :
3909 1208303144 : ctx = isl_map_get_ctx(map);
3910 1208303144 : map = isl_map_sort_divs(map);
3911 1208303144 : map = isl_map_cow(map);
3912 :
3913 1208303144 : if (!map)
3914 0 : return NULL;
3915 :
3916 1208303144 : n = map->n;
3917 :
3918 1208303144 : info = isl_calloc_array(map->ctx, struct isl_coalesce_info, n);
3919 1208303144 : if (!info)
3920 0 : goto error;
3921 :
3922 4107136064 : for (i = 0; i < map->n; ++i) {
3923 2898832920 : map->p[i] = isl_basic_map_reduce_coefficients(map->p[i]);
3924 2898832920 : if (!map->p[i])
3925 0 : goto error;
3926 2898832920 : info[i].bmap = isl_basic_map_copy(map->p[i]);
3927 2898832920 : info[i].tab = isl_tab_from_basic_map(info[i].bmap, 0);
3928 2898832920 : if (!info[i].tab)
3929 0 : goto error;
3930 2898832920 : if (!ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_NO_IMPLICIT))
3931 2898739628 : if (isl_tab_detect_implicit_equalities(info[i].tab) < 0)
3932 0 : goto error;
3933 5797665840 : info[i].bmap = isl_tab_make_equalities_explicit(info[i].tab,
3934 2898832920 : info[i].bmap);
3935 2898832920 : if (!info[i].bmap)
3936 0 : goto error;
3937 2898832920 : if (!ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_NO_REDUNDANT))
3938 2898744071 : if (isl_tab_detect_redundant(info[i].tab) < 0)
3939 0 : goto error;
3940 2898832920 : if (coalesce_info_set_hull_hash(&info[i]) < 0)
3941 0 : goto error;
3942 : }
3943 4107136064 : for (i = map->n - 1; i >= 0; --i)
3944 2898832920 : if (info[i].tab->empty)
3945 38817 : drop(&info[i]);
3946 :
3947 1208303144 : if (coalesce(ctx, n, info) < 0)
3948 0 : goto error;
3949 :
3950 1208303144 : map = update_basic_maps(map, n, info);
3951 :
3952 1208303144 : clear_coalesce_info(n, info);
3953 :
3954 1208303144 : return map;
3955 : error:
3956 0 : clear_coalesce_info(n, info);
3957 0 : isl_map_free(map);
3958 0 : return NULL;
3959 : }
3960 :
3961 : /* For each pair of basic sets in the set, check if the union of the two
3962 : * can be represented by a single basic set.
3963 : * If so, replace the pair by the single basic set and start over.
3964 : */
3965 1218389894 : struct isl_set *isl_set_coalesce(struct isl_set *set)
3966 : {
3967 1218389894 : return set_from_map(isl_map_coalesce(set_to_map(set)));
3968 : }
|
