nexmon – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2010 INRIA Saclay
4 * Copyright 2012 Ecole Normale Superieure
5 *
6 * Use of this software is governed by the GNU LGPLv2.1 license
7 *
8 * Written by Sven Verdoolaege, K.U.Leuven, Departement
9 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
10 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
11 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
12 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
13 */
14  
15 #include "isl_map_private.h"
16 #include <isl/seq.h>
17 #include <isl/options.h>
18 #include "isl_tab.h"
19 #include <isl_mat_private.h>
20 #include <isl_local_space_private.h>
21  
22 #define STATUS_ERROR -1
23 #define STATUS_REDUNDANT 1
24 #define STATUS_VALID 2
25 #define STATUS_SEPARATE 3
26 #define STATUS_CUT 4
27 #define STATUS_ADJ_EQ 5
28 #define STATUS_ADJ_INEQ 6
29  
30 static int status_in(isl_int *ineq, struct isl_tab *tab)
31 {
32 enum isl_ineq_type type = isl_tab_ineq_type(tab, ineq);
33 switch (type) {
34 default:
35 case isl_ineq_error: return STATUS_ERROR;
36 case isl_ineq_redundant: return STATUS_VALID;
37 case isl_ineq_separate: return STATUS_SEPARATE;
38 case isl_ineq_cut: return STATUS_CUT;
39 case isl_ineq_adj_eq: return STATUS_ADJ_EQ;
40 case isl_ineq_adj_ineq: return STATUS_ADJ_INEQ;
41 }
42 }
43  
44 /* Compute the position of the equalities of basic map "bmap_i"
45 * with respect to the basic map represented by "tab_j".
46 * The resulting array has twice as many entries as the number
47 * of equalities corresponding to the two inequalties to which
48 * each equality corresponds.
49 */
50 static int *eq_status_in(__isl_keep isl_basic_map *bmap_i,
51 struct isl_tab *tab_j)
52 {
53 int k, l;
54 int *eq = isl_calloc_array(bmap_i->ctx, int, 2 * bmap_i->n_eq);
55 unsigned dim;
56  
57 dim = isl_basic_map_total_dim(bmap_i);
58 for (k = 0; k < bmap_i->n_eq; ++k) {
59 for (l = 0; l < 2; ++l) {
60 isl_seq_neg(bmap_i->eq[k], bmap_i->eq[k], 1+dim);
61 eq[2 * k + l] = status_in(bmap_i->eq[k], tab_j);
62 if (eq[2 * k + l] == STATUS_ERROR)
63 goto error;
64 }
65 if (eq[2 * k] == STATUS_SEPARATE ||
66 eq[2 * k + 1] == STATUS_SEPARATE)
67 break;
68 }
69  
70 return eq;
71 error:
72 free(eq);
73 return NULL;
74 }
75  
76 /* Compute the position of the inequalities of basic map "bmap_i"
77 * (also represented by "tab_i", if not NULL) with respect to the basic map
78 * represented by "tab_j".
79 */
80 static int *ineq_status_in(__isl_keep isl_basic_map *bmap_i,
81 struct isl_tab *tab_i, struct isl_tab *tab_j)
82 {
83 int k;
84 unsigned n_eq = bmap_i->n_eq;
85 int *ineq = isl_calloc_array(bmap_i->ctx, int, bmap_i->n_ineq);
86  
87 for (k = 0; k < bmap_i->n_ineq; ++k) {
88 if (tab_i && isl_tab_is_redundant(tab_i, n_eq + k)) {
89 ineq[k] = STATUS_REDUNDANT;
90 continue;
91 }
92 ineq[k] = status_in(bmap_i->ineq[k], tab_j);
93 if (ineq[k] == STATUS_ERROR)
94 goto error;
95 if (ineq[k] == STATUS_SEPARATE)
96 break;
97 }
98  
99 return ineq;
100 error:
101 free(ineq);
102 return NULL;
103 }
104  
105 static int any(int *con, unsigned len, int status)
106 {
107 int i;
108  
109 for (i = 0; i < len ; ++i)
110 if (con[i] == status)
111 return 1;
112 return 0;
113 }
114  
115 static int count(int *con, unsigned len, int status)
116 {
117 int i;
118 int c = 0;
119  
120 for (i = 0; i < len ; ++i)
121 if (con[i] == status)
122 c++;
123 return c;
124 }
125  
126 static int all(int *con, unsigned len, int status)
127 {
128 int i;
129  
130 for (i = 0; i < len ; ++i) {
131 if (con[i] == STATUS_REDUNDANT)
132 continue;
133 if (con[i] != status)
134 return 0;
135 }
136 return 1;
137 }
138  
139 static void drop(struct isl_map *map, int i, struct isl_tab **tabs)
140 {
141 isl_basic_map_free(map->p[i]);
142 isl_tab_free(tabs[i]);
143  
144 if (i != map->n - 1) {
145 map->p[i] = map->p[map->n - 1];
146 tabs[i] = tabs[map->n - 1];
147 }
148 tabs[map->n - 1] = NULL;
149 map->n--;
150 }
151  
152 /* Replace the pair of basic maps i and j by the basic map bounded
153 * by the valid constraints in both basic maps and the constraint
154 * in extra (if not NULL).
155 */
156 static int fuse(struct isl_map *map, int i, int j,
157 struct isl_tab **tabs, int *eq_i, int *ineq_i, int *eq_j, int *ineq_j,
158 __isl_keep isl_mat *extra)
159 {
160 int k, l;
161 struct isl_basic_map *fused = NULL;
162 struct isl_tab *fused_tab = NULL;
163 unsigned total = isl_basic_map_total_dim(map->p[i]);
164 unsigned extra_rows = extra ? extra->n_row : 0;
165  
166 fused = isl_basic_map_alloc_space(isl_space_copy(map->p[i]->dim),
167 map->p[i]->n_div,
168 map->p[i]->n_eq + map->p[j]->n_eq,
169 map->p[i]->n_ineq + map->p[j]->n_ineq + extra_rows);
170 if (!fused)
171 goto error;
172  
173 for (k = 0; k < map->p[i]->n_eq; ++k) {
174 if (eq_i && (eq_i[2 * k] != STATUS_VALID ||
175 eq_i[2 * k + 1] != STATUS_VALID))
176 continue;
177 l = isl_basic_map_alloc_equality(fused);
178 if (l < 0)
179 goto error;
180 isl_seq_cpy(fused->eq[l], map->p[i]->eq[k], 1 + total);
181 }
182  
183 for (k = 0; k < map->p[j]->n_eq; ++k) {
184 if (eq_j && (eq_j[2 * k] != STATUS_VALID ||
185 eq_j[2 * k + 1] != STATUS_VALID))
186 continue;
187 l = isl_basic_map_alloc_equality(fused);
188 if (l < 0)
189 goto error;
190 isl_seq_cpy(fused->eq[l], map->p[j]->eq[k], 1 + total);
191 }
192  
193 for (k = 0; k < map->p[i]->n_ineq; ++k) {
194 if (ineq_i[k] != STATUS_VALID)
195 continue;
196 l = isl_basic_map_alloc_inequality(fused);
197 if (l < 0)
198 goto error;
199 isl_seq_cpy(fused->ineq[l], map->p[i]->ineq[k], 1 + total);
200 }
201  
202 for (k = 0; k < map->p[j]->n_ineq; ++k) {
203 if (ineq_j[k] != STATUS_VALID)
204 continue;
205 l = isl_basic_map_alloc_inequality(fused);
206 if (l < 0)
207 goto error;
208 isl_seq_cpy(fused->ineq[l], map->p[j]->ineq[k], 1 + total);
209 }
210  
211 for (k = 0; k < map->p[i]->n_div; ++k) {
212 int l = isl_basic_map_alloc_div(fused);
213 if (l < 0)
214 goto error;
215 isl_seq_cpy(fused->div[l], map->p[i]->div[k], 1 + 1 + total);
216 }
217  
218 for (k = 0; k < extra_rows; ++k) {
219 l = isl_basic_map_alloc_inequality(fused);
220 if (l < 0)
221 goto error;
222 isl_seq_cpy(fused->ineq[l], extra->row[k], 1 + total);
223 }
224  
225 fused = isl_basic_map_gauss(fused, NULL);
226 ISL_F_SET(fused, ISL_BASIC_MAP_FINAL);
227 if (ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_RATIONAL) &&
228 ISL_F_ISSET(map->p[j], ISL_BASIC_MAP_RATIONAL))
229 ISL_F_SET(fused, ISL_BASIC_MAP_RATIONAL);
230  
231 fused_tab = isl_tab_from_basic_map(fused, 0);
232 if (isl_tab_detect_redundant(fused_tab) < 0)
233 goto error;
234  
235 isl_basic_map_free(map->p[i]);
236 map->p[i] = fused;
237 isl_tab_free(tabs[i]);
238 tabs[i] = fused_tab;
239 drop(map, j, tabs);
240  
241 return 1;
242 error:
243 isl_tab_free(fused_tab);
244 isl_basic_map_free(fused);
245 return -1;
246 }
247  
248 /* Given a pair of basic maps i and j such that all constraints are either
249 * "valid" or "cut", check if the facets corresponding to the "cut"
250 * constraints of i lie entirely within basic map j.
251 * If so, replace the pair by the basic map consisting of the valid
252 * constraints in both basic maps.
253 *
254 * To see that we are not introducing any extra points, call the
255 * two basic maps A and B and the resulting map U and let x
256 * be an element of U \setminus ( A \cup B ).
257 * Then there is a pair of cut constraints c_1 and c_2 in A and B such that x
258 * violates them. Let X be the intersection of U with the opposites
259 * of these constraints. Then x \in X.
260 * The facet corresponding to c_1 contains the corresponding facet of A.
261 * This facet is entirely contained in B, so c_2 is valid on the facet.
262 * However, since it is also (part of) a facet of X, -c_2 is also valid
263 * on the facet. This means c_2 is saturated on the facet, so c_1 and
264 * c_2 must be opposites of each other, but then x could not violate
265 * both of them.
266 */
267 static int check_facets(struct isl_map *map, int i, int j,
268 struct isl_tab **tabs, int *ineq_i, int *ineq_j)
269 {
270 int k, l;
271 struct isl_tab_undo *snap;
272 unsigned n_eq = map->p[i]->n_eq;
273  
274 snap = isl_tab_snap(tabs[i]);
275  
276 for (k = 0; k < map->p[i]->n_ineq; ++k) {
277 if (ineq_i[k] != STATUS_CUT)
278 continue;
279 if (isl_tab_select_facet(tabs[i], n_eq + k) < 0)
280 return -1;
281 for (l = 0; l < map->p[j]->n_ineq; ++l) {
282 int stat;
283 if (ineq_j[l] != STATUS_CUT)
284 continue;
285 stat = status_in(map->p[j]->ineq[l], tabs[i]);
286 if (stat != STATUS_VALID)
287 break;
288 }
289 if (isl_tab_rollback(tabs[i], snap) < 0)
290 return -1;
291 if (l < map->p[j]->n_ineq)
292 break;
293 }
294  
295 if (k < map->p[i]->n_ineq)
296 /* BAD CUT PAIR */
297 return 0;
298 return fuse(map, i, j, tabs, NULL, ineq_i, NULL, ineq_j, NULL);
299 }
300  
301 /* Both basic maps have at least one inequality with and adjacent
302 * (but opposite) inequality in the other basic map.
303 * Check that there are no cut constraints and that there is only
304 * a single pair of adjacent inequalities.
305 * If so, we can replace the pair by a single basic map described
306 * by all but the pair of adjacent inequalities.
307 * Any additional points introduced lie strictly between the two
308 * adjacent hyperplanes and can therefore be integral.
309 *
310 * ____ _____
311 * / ||\ / \
312 * / || \ / \
313 * \ || \ => \ \
314 * \ || / \ /
315 * \___||_/ \_____/
316 *
317 * The test for a single pair of adjancent inequalities is important
318 * for avoiding the combination of two basic maps like the following
319 *
320 * /|
321 * / |
322 * /__|
323 * _____
324 * | |
325 * | |
326 * |___|
327 */
328 static int check_adj_ineq(struct isl_map *map, int i, int j,
329 struct isl_tab **tabs, int *ineq_i, int *ineq_j)
330 {
331 int changed = 0;
332  
333 if (any(ineq_i, map->p[i]->n_ineq, STATUS_CUT) ||
334 any(ineq_j, map->p[j]->n_ineq, STATUS_CUT))
335 /* ADJ INEQ CUT */
336 ;
337 else if (count(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_INEQ) == 1 &&
338 count(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_INEQ) == 1)
339 changed = fuse(map, i, j, tabs, NULL, ineq_i, NULL, ineq_j, NULL);
340 /* else ADJ INEQ TOO MANY */
341  
342 return changed;
343 }
344  
345 /* Check if basic map "i" contains the basic map represented
346 * by the tableau "tab".
347 */
348 static int contains(struct isl_map *map, int i, int *ineq_i,
349 struct isl_tab *tab)
350 {
351 int k, l;
352 unsigned dim;
353  
354 dim = isl_basic_map_total_dim(map->p[i]);
355 for (k = 0; k < map->p[i]->n_eq; ++k) {
356 for (l = 0; l < 2; ++l) {
357 int stat;
358 isl_seq_neg(map->p[i]->eq[k], map->p[i]->eq[k], 1+dim);
359 stat = status_in(map->p[i]->eq[k], tab);
360 if (stat != STATUS_VALID)
361 return 0;
362 }
363 }
364  
365 for (k = 0; k < map->p[i]->n_ineq; ++k) {
366 int stat;
367 if (ineq_i[k] == STATUS_REDUNDANT)
368 continue;
369 stat = status_in(map->p[i]->ineq[k], tab);
370 if (stat != STATUS_VALID)
371 return 0;
372 }
373 return 1;
374 }
375  
376 /* Basic map "i" has an inequality "k" that is adjacent to some equality
377 * of basic map "j". All the other inequalities are valid for "j".
378 * Check if basic map "j" forms an extension of basic map "i".
379 *
380 * In particular, we relax constraint "k", compute the corresponding
381 * facet and check whether it is included in the other basic map.
382 * If so, we know that relaxing the constraint extends the basic
383 * map with exactly the other basic map (we already know that this
384 * other basic map is included in the extension, because there
385 * were no "cut" inequalities in "i") and we can replace the
386 * two basic maps by thie extension.
387 * ____ _____
388 * / || / |
389 * / || / |
390 * \ || => \ |
391 * \ || \ |
392 * \___|| \____|
393 */
394 static int is_extension(struct isl_map *map, int i, int j, int k,
395 struct isl_tab **tabs, int *eq_i, int *ineq_i, int *eq_j, int *ineq_j)
396 {
397 int changed = 0;
398 int super;
399 struct isl_tab_undo *snap, *snap2;
400 unsigned n_eq = map->p[i]->n_eq;
401  
402 if (isl_tab_is_equality(tabs[i], n_eq + k))
403 return 0;
404  
405 snap = isl_tab_snap(tabs[i]);
406 tabs[i] = isl_tab_relax(tabs[i], n_eq + k);
407 snap2 = isl_tab_snap(tabs[i]);
408 if (isl_tab_select_facet(tabs[i], n_eq + k) < 0)
409 return -1;
410 super = contains(map, j, ineq_j, tabs[i]);
411 if (super) {
412 if (isl_tab_rollback(tabs[i], snap2) < 0)
413 return -1;
414 map->p[i] = isl_basic_map_cow(map->p[i]);
415 if (!map->p[i])
416 return -1;
417 isl_int_add_ui(map->p[i]->ineq[k][0], map->p[i]->ineq[k][0], 1);
418 ISL_F_SET(map->p[i], ISL_BASIC_MAP_FINAL);
419 drop(map, j, tabs);
420 changed = 1;
421 } else
422 if (isl_tab_rollback(tabs[i], snap) < 0)
423 return -1;
424  
425 return changed;
426 }
427  
428 /* Data structure that keeps track of the wrapping constraints
429 * and of information to bound the coefficients of those constraints.
430 *
431 * bound is set if we want to apply a bound on the coefficients
432 * mat contains the wrapping constraints
433 * max is the bound on the coefficients (if bound is set)
434 */
435 struct isl_wraps {
436 int bound;
437 isl_mat *mat;
438 isl_int max;
439 };
440  
441 /* Update wraps->max to be greater than or equal to the coefficients
442 * in the equalities and inequalities of bmap that can be removed if we end up
443 * applying wrapping.
444 */
445 static void wraps_update_max(struct isl_wraps *wraps,
446 __isl_keep isl_basic_map *bmap, int *eq, int *ineq)
447 {
448 int k;
449 isl_int max_k;
450 unsigned total = isl_basic_map_total_dim(bmap);
451  
452 isl_int_init(max_k);
453  
454 for (k = 0; k < bmap->n_eq; ++k) {
455 if (eq[2 * k] == STATUS_VALID &&
456 eq[2 * k + 1] == STATUS_VALID)
457 continue;
458 isl_seq_abs_max(bmap->eq[k] + 1, total, &max_k);
459 if (isl_int_abs_gt(max_k, wraps->max))
460 isl_int_set(wraps->max, max_k);
461 }
462  
463 for (k = 0; k < bmap->n_ineq; ++k) {
464 if (ineq[k] == STATUS_VALID || ineq[k] == STATUS_REDUNDANT)
465 continue;
466 isl_seq_abs_max(bmap->ineq[k] + 1, total, &max_k);
467 if (isl_int_abs_gt(max_k, wraps->max))
468 isl_int_set(wraps->max, max_k);
469 }
470  
471 isl_int_clear(max_k);
472 }
473  
474 /* Initialize the isl_wraps data structure.
475 * If we want to bound the coefficients of the wrapping constraints,
476 * we set wraps->max to the largest coefficient
477 * in the equalities and inequalities that can be removed if we end up
478 * applying wrapping.
479 */
480 static void wraps_init(struct isl_wraps *wraps, __isl_take isl_mat *mat,
481 __isl_keep isl_map *map, int i, int j,
482 int *eq_i, int *ineq_i, int *eq_j, int *ineq_j)
483 {
484 isl_ctx *ctx;
485  
486 wraps->bound = 0;
487 wraps->mat = mat;
488 if (!mat)
489 return;
490 ctx = isl_mat_get_ctx(mat);
491 wraps->bound = isl_options_get_coalesce_bounded_wrapping(ctx);
492 if (!wraps->bound)
493 return;
494 isl_int_init(wraps->max);
495 isl_int_set_si(wraps->max, 0);
496 wraps_update_max(wraps, map->p[i], eq_i, ineq_i);
497 wraps_update_max(wraps, map->p[j], eq_j, ineq_j);
498 }
499  
500 /* Free the contents of the isl_wraps data structure.
501 */
502 static void wraps_free(struct isl_wraps *wraps)
503 {
504 isl_mat_free(wraps->mat);
505 if (wraps->bound)
506 isl_int_clear(wraps->max);
507 }
508  
509 /* Is the wrapping constraint in row "row" allowed?
510 *
511 * If wraps->bound is set, we check that none of the coefficients
512 * is greater than wraps->max.
513 */
514 static int allow_wrap(struct isl_wraps *wraps, int row)
515 {
516 int i;
517  
518 if (!wraps->bound)
519 return 1;
520  
521 for (i = 1; i < wraps->mat->n_col; ++i)
522 if (isl_int_abs_gt(wraps->mat->row[row][i], wraps->max))
523 return 0;
524  
525 return 1;
526 }
527  
528 /* For each non-redundant constraint in "bmap" (as determined by "tab"),
529 * wrap the constraint around "bound" such that it includes the whole
530 * set "set" and append the resulting constraint to "wraps".
531 * "wraps" is assumed to have been pre-allocated to the appropriate size.
532 * wraps->n_row is the number of actual wrapped constraints that have
533 * been added.
534 * If any of the wrapping problems results in a constraint that is
535 * identical to "bound", then this means that "set" is unbounded in such
536 * way that no wrapping is possible. If this happens then wraps->n_row
537 * is reset to zero.
538 * Similarly, if we want to bound the coefficients of the wrapping
539 * constraints and a newly added wrapping constraint does not
540 * satisfy the bound, then wraps->n_row is also reset to zero.
541 */
542 static int add_wraps(struct isl_wraps *wraps, __isl_keep isl_basic_map *bmap,
543 struct isl_tab *tab, isl_int *bound, __isl_keep isl_set *set)
544 {
545 int l;
546 int w;
547 unsigned total = isl_basic_map_total_dim(bmap);
548  
549 w = wraps->mat->n_row;
550  
551 for (l = 0; l < bmap->n_ineq; ++l) {
552 if (isl_seq_is_neg(bound, bmap->ineq[l], 1 + total))
553 continue;
554 if (isl_seq_eq(bound, bmap->ineq[l], 1 + total))
555 continue;
556 if (isl_tab_is_redundant(tab, bmap->n_eq + l))
557 continue;
558  
559 isl_seq_cpy(wraps->mat->row[w], bound, 1 + total);
560 if (!isl_set_wrap_facet(set, wraps->mat->row[w], bmap->ineq[l]))
561 return -1;
562 if (isl_seq_eq(wraps->mat->row[w], bound, 1 + total))
563 goto unbounded;
564 if (!allow_wrap(wraps, w))
565 goto unbounded;
566 ++w;
567 }
568 for (l = 0; l < bmap->n_eq; ++l) {
569 if (isl_seq_is_neg(bound, bmap->eq[l], 1 + total))
570 continue;
571 if (isl_seq_eq(bound, bmap->eq[l], 1 + total))
572 continue;
573  
574 isl_seq_cpy(wraps->mat->row[w], bound, 1 + total);
575 isl_seq_neg(wraps->mat->row[w + 1], bmap->eq[l], 1 + total);
576 if (!isl_set_wrap_facet(set, wraps->mat->row[w],
577 wraps->mat->row[w + 1]))
578 return -1;
579 if (isl_seq_eq(wraps->mat->row[w], bound, 1 + total))
580 goto unbounded;
581 if (!allow_wrap(wraps, w))
582 goto unbounded;
583 ++w;
584  
585 isl_seq_cpy(wraps->mat->row[w], bound, 1 + total);
586 if (!isl_set_wrap_facet(set, wraps->mat->row[w], bmap->eq[l]))
587 return -1;
588 if (isl_seq_eq(wraps->mat->row[w], bound, 1 + total))
589 goto unbounded;
590 if (!allow_wrap(wraps, w))
591 goto unbounded;
592 ++w;
593 }
594  
595 wraps->mat->n_row = w;
596 return 0;
597 unbounded:
598 wraps->mat->n_row = 0;
599 return 0;
600 }
601  
602 /* Check if the constraints in "wraps" from "first" until the last
603 * are all valid for the basic set represented by "tab".
604 * If not, wraps->n_row is set to zero.
605 */
606 static int check_wraps(__isl_keep isl_mat *wraps, int first,
607 struct isl_tab *tab)
608 {
609 int i;
610  
611 for (i = first; i < wraps->n_row; ++i) {
612 enum isl_ineq_type type;
613 type = isl_tab_ineq_type(tab, wraps->row[i]);
614 if (type == isl_ineq_error)
615 return -1;
616 if (type == isl_ineq_redundant)
617 continue;
618 wraps->n_row = 0;
619 return 0;
620 }
621  
622 return 0;
623 }
624  
625 /* Return a set that corresponds to the non-redudant constraints
626 * (as recorded in tab) of bmap.
627 *
628 * It's important to remove the redundant constraints as some
629 * of the other constraints may have been modified after the
630 * constraints were marked redundant.
631 * In particular, a constraint may have been relaxed.
632 * Redundant constraints are ignored when a constraint is relaxed
633 * and should therefore continue to be ignored ever after.
634 * Otherwise, the relaxation might be thwarted by some of
635 * these constraints.
636 */
637 static __isl_give isl_set *set_from_updated_bmap(__isl_keep isl_basic_map *bmap,
638 struct isl_tab *tab)
639 {
640 bmap = isl_basic_map_copy(bmap);
641 bmap = isl_basic_map_cow(bmap);
642 bmap = isl_basic_map_update_from_tab(bmap, tab);
643 return isl_set_from_basic_set(isl_basic_map_underlying_set(bmap));
644 }
645  
646 /* Given a basic set i with a constraint k that is adjacent to either the
647 * whole of basic set j or a facet of basic set j, check if we can wrap
648 * both the facet corresponding to k and the facet of j (or the whole of j)
649 * around their ridges to include the other set.
650 * If so, replace the pair of basic sets by their union.
651 *
652 * All constraints of i (except k) are assumed to be valid for j.
653 *
654 * However, the constraints of j may not be valid for i and so
655 * we have to check that the wrapping constraints for j are valid for i.
656 *
657 * In the case where j has a facet adjacent to i, tab[j] is assumed
658 * to have been restricted to this facet, so that the non-redundant
659 * constraints in tab[j] are the ridges of the facet.
660 * Note that for the purpose of wrapping, it does not matter whether
661 * we wrap the ridges of i around the whole of j or just around
662 * the facet since all the other constraints are assumed to be valid for j.
663 * In practice, we wrap to include the whole of j.
664 * ____ _____
665 * / | / \
666 * / || / |
667 * \ || => \ |
668 * \ || \ |
669 * \___|| \____|
670 *
671 */
672 static int can_wrap_in_facet(struct isl_map *map, int i, int j, int k,
673 struct isl_tab **tabs, int *eq_i, int *ineq_i, int *eq_j, int *ineq_j)
674 {
675 int changed = 0;
676 struct isl_wraps wraps;
677 isl_mat *mat;
678 struct isl_set *set_i = NULL;
679 struct isl_set *set_j = NULL;
680 struct isl_vec *bound = NULL;
681 unsigned total = isl_basic_map_total_dim(map->p[i]);
682 struct isl_tab_undo *snap;
683 int n;
684  
685 set_i = set_from_updated_bmap(map->p[i], tabs[i]);
686 set_j = set_from_updated_bmap(map->p[j], tabs[j]);
687 mat = isl_mat_alloc(map->ctx, 2 * (map->p[i]->n_eq + map->p[j]->n_eq) +
688 map->p[i]->n_ineq + map->p[j]->n_ineq,
689 1 + total);
690 wraps_init(&wraps, mat, map, i, j, eq_i, ineq_i, eq_j, ineq_j);
691 bound = isl_vec_alloc(map->ctx, 1 + total);
692 if (!set_i || !set_j || !wraps.mat || !bound)
693 goto error;
694  
695 isl_seq_cpy(bound->el, map->p[i]->ineq[k], 1 + total);
696 isl_int_add_ui(bound->el[0], bound->el[0], 1);
697  
698 isl_seq_cpy(wraps.mat->row[0], bound->el, 1 + total);
699 wraps.mat->n_row = 1;
700  
701 if (add_wraps(&wraps, map->p[j], tabs[j], bound->el, set_i) < 0)
702 goto error;
703 if (!wraps.mat->n_row)
704 goto unbounded;
705  
706 snap = isl_tab_snap(tabs[i]);
707  
708 if (isl_tab_select_facet(tabs[i], map->p[i]->n_eq + k) < 0)
709 goto error;
710 if (isl_tab_detect_redundant(tabs[i]) < 0)
711 goto error;
712  
713 isl_seq_neg(bound->el, map->p[i]->ineq[k], 1 + total);
714  
715 n = wraps.mat->n_row;
716 if (add_wraps(&wraps, map->p[i], tabs[i], bound->el, set_j) < 0)
717 goto error;
718  
719 if (isl_tab_rollback(tabs[i], snap) < 0)
720 goto error;
721 if (check_wraps(wraps.mat, n, tabs[i]) < 0)
722 goto error;
723 if (!wraps.mat->n_row)
724 goto unbounded;
725  
726 changed = fuse(map, i, j, tabs, eq_i, ineq_i, eq_j, ineq_j, wraps.mat);
727  
728 unbounded:
729 wraps_free(&wraps);
730  
731 isl_set_free(set_i);
732 isl_set_free(set_j);
733  
734 isl_vec_free(bound);
735  
736 return changed;
737 error:
738 wraps_free(&wraps);
739 isl_vec_free(bound);
740 isl_set_free(set_i);
741 isl_set_free(set_j);
742 return -1;
743 }
744  
745 /* Set the is_redundant property of the "n" constraints in "cuts",
746 * except "k" to "v".
747 * This is a fairly tricky operation as it bypasses isl_tab.c.
748 * The reason we want to temporarily mark some constraints redundant
749 * is that we want to ignore them in add_wraps.
750 *
751 * Initially all cut constraints are non-redundant, but the
752 * selection of a facet right before the call to this function
753 * may have made some of them redundant.
754 * Likewise, the same constraints are marked non-redundant
755 * in the second call to this function, before they are officially
756 * made non-redundant again in the subsequent rollback.
757 */
758 static void set_is_redundant(struct isl_tab *tab, unsigned n_eq,
759 int *cuts, int n, int k, int v)
760 {
761 int l;
762  
763 for (l = 0; l < n; ++l) {
764 if (l == k)
765 continue;
766 tab->con[n_eq + cuts[l]].is_redundant = v;
767 }
768 }
769  
770 /* Given a pair of basic maps i and j such that j sticks out
771 * of i at n cut constraints, each time by at most one,
772 * try to compute wrapping constraints and replace the two
773 * basic maps by a single basic map.
774 * The other constraints of i are assumed to be valid for j.
775 *
776 * The facets of i corresponding to the cut constraints are
777 * wrapped around their ridges, except those ridges determined
778 * by any of the other cut constraints.
779 * The intersections of cut constraints need to be ignored
780 * as the result of wrapping one cut constraint around another
781 * would result in a constraint cutting the union.
782 * In each case, the facets are wrapped to include the union
783 * of the two basic maps.
784 *
785 * The pieces of j that lie at an offset of exactly one from
786 * one of the cut constraints of i are wrapped around their edges.
787 * Here, there is no need to ignore intersections because we
788 * are wrapping around the union of the two basic maps.
789 *
790 * If any wrapping fails, i.e., if we cannot wrap to touch
791 * the union, then we give up.
792 * Otherwise, the pair of basic maps is replaced by their union.
793 */
794 static int wrap_in_facets(struct isl_map *map, int i, int j,
795 int *cuts, int n, struct isl_tab **tabs,
796 int *eq_i, int *ineq_i, int *eq_j, int *ineq_j)
797 {
798 int changed = 0;
799 struct isl_wraps wraps;
800 isl_mat *mat;
801 isl_set *set = NULL;
802 isl_vec *bound = NULL;
803 unsigned total = isl_basic_map_total_dim(map->p[i]);
804 int max_wrap;
805 int k;
806 struct isl_tab_undo *snap_i, *snap_j;
807  
808 if (isl_tab_extend_cons(tabs[j], 1) < 0)
809 goto error;
810  
811 max_wrap = 2 * (map->p[i]->n_eq + map->p[j]->n_eq) +
812 map->p[i]->n_ineq + map->p[j]->n_ineq;
813 max_wrap *= n;
814  
815 set = isl_set_union(set_from_updated_bmap(map->p[i], tabs[i]),
816 set_from_updated_bmap(map->p[j], tabs[j]));
817 mat = isl_mat_alloc(map->ctx, max_wrap, 1 + total);
818 wraps_init(&wraps, mat, map, i, j, eq_i, ineq_i, eq_j, ineq_j);
819 bound = isl_vec_alloc(map->ctx, 1 + total);
820 if (!set || !wraps.mat || !bound)
821 goto error;
822  
823 snap_i = isl_tab_snap(tabs[i]);
824 snap_j = isl_tab_snap(tabs[j]);
825  
826 wraps.mat->n_row = 0;
827  
828 for (k = 0; k < n; ++k) {
829 if (isl_tab_select_facet(tabs[i], map->p[i]->n_eq + cuts[k]) < 0)
830 goto error;
831 if (isl_tab_detect_redundant(tabs[i]) < 0)
832 goto error;
833 set_is_redundant(tabs[i], map->p[i]->n_eq, cuts, n, k, 1);
834  
835 isl_seq_neg(bound->el, map->p[i]->ineq[cuts[k]], 1 + total);
836 if (!tabs[i]->empty &&
837 add_wraps(&wraps, map->p[i], tabs[i], bound->el, set) < 0)
838 goto error;
839  
840 set_is_redundant(tabs[i], map->p[i]->n_eq, cuts, n, k, 0);
841 if (isl_tab_rollback(tabs[i], snap_i) < 0)
842 goto error;
843  
844 if (tabs[i]->empty)
845 break;
846 if (!wraps.mat->n_row)
847 break;
848  
849 isl_seq_cpy(bound->el, map->p[i]->ineq[cuts[k]], 1 + total);
850 isl_int_add_ui(bound->el[0], bound->el[0], 1);
851 if (isl_tab_add_eq(tabs[j], bound->el) < 0)
852 goto error;
853 if (isl_tab_detect_redundant(tabs[j]) < 0)
854 goto error;
855  
856 if (!tabs[j]->empty &&
857 add_wraps(&wraps, map->p[j], tabs[j], bound->el, set) < 0)
858 goto error;
859  
860 if (isl_tab_rollback(tabs[j], snap_j) < 0)
861 goto error;
862  
863 if (!wraps.mat->n_row)
864 break;
865 }
866  
867 if (k == n)
868 changed = fuse(map, i, j, tabs,
869 eq_i, ineq_i, eq_j, ineq_j, wraps.mat);
870  
871 isl_vec_free(bound);
872 wraps_free(&wraps);
873 isl_set_free(set);
874  
875 return changed;
876 error:
877 isl_vec_free(bound);
878 wraps_free(&wraps);
879 isl_set_free(set);
880 return -1;
881 }
882  
883 /* Given two basic sets i and j such that i has no cut equalities,
884 * check if relaxing all the cut inequalities of i by one turns
885 * them into valid constraint for j and check if we can wrap in
886 * the bits that are sticking out.
887 * If so, replace the pair by their union.
888 *
889 * We first check if all relaxed cut inequalities of i are valid for j
890 * and then try to wrap in the intersections of the relaxed cut inequalities
891 * with j.
892 *
893 * During this wrapping, we consider the points of j that lie at a distance
894 * of exactly 1 from i. In particular, we ignore the points that lie in
895 * between this lower-dimensional space and the basic map i.
896 * We can therefore only apply this to integer maps.
897 * ____ _____
898 * / ___|_ / \
899 * / | | / |
900 * \ | | => \ |
901 * \|____| \ |
902 * \___| \____/
903 *
904 * _____ ______
905 * | ____|_ | \
906 * | | | | |
907 * | | | => | |
908 * |_| | | |
909 * |_____| \______|
910 *
911 * _______
912 * | |
913 * | |\ |
914 * | | \ |
915 * | | \ |
916 * | | \|
917 * | | \
918 * | |_____\
919 * | |
920 * |_______|
921 *
922 * Wrapping can fail if the result of wrapping one of the facets
923 * around its edges does not produce any new facet constraint.
924 * In particular, this happens when we try to wrap in unbounded sets.
925 *
926 * _______________________________________________________________________
927 * |
928 * | ___
929 * | | |
930 * |_| |_________________________________________________________________
931 * |___|
932 *
933 * The following is not an acceptable result of coalescing the above two
934 * sets as it includes extra integer points.
935 * _______________________________________________________________________
936 * |
937 * |
938 * |
939 * |
940 * \______________________________________________________________________
941 */
942 static int can_wrap_in_set(struct isl_map *map, int i, int j,
943 struct isl_tab **tabs, int *eq_i, int *ineq_i, int *eq_j, int *ineq_j)
944 {
945 int changed = 0;
946 int k, m;
947 int n;
948 int *cuts = NULL;
949  
950 if (ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_RATIONAL) ||
951 ISL_F_ISSET(map->p[j], ISL_BASIC_MAP_RATIONAL))
952 return 0;
953  
954 n = count(ineq_i, map->p[i]->n_ineq, STATUS_CUT);
955 if (n == 0)
956 return 0;
957  
958 cuts = isl_alloc_array(map->ctx, int, n);
959 if (!cuts)
960 return -1;
961  
962 for (k = 0, m = 0; m < n; ++k) {
963 enum isl_ineq_type type;
964  
965 if (ineq_i[k] != STATUS_CUT)
966 continue;
967  
968 isl_int_add_ui(map->p[i]->ineq[k][0], map->p[i]->ineq[k][0], 1);
969 type = isl_tab_ineq_type(tabs[j], map->p[i]->ineq[k]);
970 isl_int_sub_ui(map->p[i]->ineq[k][0], map->p[i]->ineq[k][0], 1);
971 if (type == isl_ineq_error)
972 goto error;
973 if (type != isl_ineq_redundant)
974 break;
975 cuts[m] = k;
976 ++m;
977 }
978  
979 if (m == n)
980 changed = wrap_in_facets(map, i, j, cuts, n, tabs,
981 eq_i, ineq_i, eq_j, ineq_j);
982  
983 free(cuts);
984  
985 return changed;
986 error:
987 free(cuts);
988 return -1;
989 }
990  
991 /* Check if either i or j has a single cut constraint that can
992 * be used to wrap in (a facet of) the other basic set.
993 * if so, replace the pair by their union.
994 */
995 static int check_wrap(struct isl_map *map, int i, int j,
996 struct isl_tab **tabs, int *eq_i, int *ineq_i, int *eq_j, int *ineq_j)
997 {
998 int changed = 0;
999  
1000 if (!any(eq_i, 2 * map->p[i]->n_eq, STATUS_CUT))
1001 changed = can_wrap_in_set(map, i, j, tabs,
1002 eq_i, ineq_i, eq_j, ineq_j);
1003 if (changed)
1004 return changed;
1005  
1006 if (!any(eq_j, 2 * map->p[j]->n_eq, STATUS_CUT))
1007 changed = can_wrap_in_set(map, j, i, tabs,
1008 eq_j, ineq_j, eq_i, ineq_i);
1009 return changed;
1010 }
1011  
1012 /* At least one of the basic maps has an equality that is adjacent
1013 * to inequality. Make sure that only one of the basic maps has
1014 * such an equality and that the other basic map has exactly one
1015 * inequality adjacent to an equality.
1016 * We call the basic map that has the inequality "i" and the basic
1017 * map that has the equality "j".
1018 * If "i" has any "cut" (in)equality, then relaxing the inequality
1019 * by one would not result in a basic map that contains the other
1020 * basic map.
1021 */
1022 static int check_adj_eq(struct isl_map *map, int i, int j,
1023 struct isl_tab **tabs, int *eq_i, int *ineq_i, int *eq_j, int *ineq_j)
1024 {
1025 int changed = 0;
1026 int k;
1027  
1028 if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_INEQ) &&
1029 any(eq_j, 2 * map->p[j]->n_eq, STATUS_ADJ_INEQ))
1030 /* ADJ EQ TOO MANY */
1031 return 0;
1032  
1033 if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_INEQ))
1034 return check_adj_eq(map, j, i, tabs,
1035 eq_j, ineq_j, eq_i, ineq_i);
1036  
1037 /* j has an equality adjacent to an inequality in i */
1038  
1039 if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_CUT))
1040 return 0;
1041 if (any(ineq_i, map->p[i]->n_ineq, STATUS_CUT))
1042 /* ADJ EQ CUT */
1043 return 0;
1044 if (count(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_EQ) != 1 ||
1045 any(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_EQ) ||
1046 any(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_INEQ) ||
1047 any(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_INEQ))
1048 /* ADJ EQ TOO MANY */
1049 return 0;
1050  
1051 for (k = 0; k < map->p[i]->n_ineq ; ++k)
1052 if (ineq_i[k] == STATUS_ADJ_EQ)
1053 break;
1054  
1055 changed = is_extension(map, i, j, k, tabs, eq_i, ineq_i, eq_j, ineq_j);
1056 if (changed)
1057 return changed;
1058  
1059 if (count(eq_j, 2 * map->p[j]->n_eq, STATUS_ADJ_INEQ) != 1)
1060 return 0;
1061  
1062 changed = can_wrap_in_facet(map, i, j, k, tabs, eq_i, ineq_i, eq_j, ineq_j);
1063  
1064 return changed;
1065 }
1066  
1067 /* The two basic maps lie on adjacent hyperplanes. In particular,
1068 * basic map "i" has an equality that lies parallel to basic map "j".
1069 * Check if we can wrap the facets around the parallel hyperplanes
1070 * to include the other set.
1071 *
1072 * We perform basically the same operations as can_wrap_in_facet,
1073 * except that we don't need to select a facet of one of the sets.
1074 * _
1075 * \\ \\
1076 * \\ => \\
1077 * \ \|
1078 *
1079 * We only allow one equality of "i" to be adjacent to an equality of "j"
1080 * to avoid coalescing
1081 *
1082 * [m, n] -> { [x, y] -> [x, 1 + y] : x >= 1 and y >= 1 and
1083 * x <= 10 and y <= 10;
1084 * [x, y] -> [1 + x, y] : x >= 1 and x <= 20 and
1085 * y >= 5 and y <= 15 }
1086 *
1087 * to
1088 *
1089 * [m, n] -> { [x, y] -> [x2, y2] : x >= 1 and 10y2 <= 20 - x + 10y and
1090 * 4y2 >= 5 + 3y and 5y2 <= 15 + 4y and
1091 * y2 <= 1 + x + y - x2 and y2 >= y and
1092 * y2 >= 1 + x + y - x2 }
1093 */
1094 static int check_eq_adj_eq(struct isl_map *map, int i, int j,
1095 struct isl_tab **tabs, int *eq_i, int *ineq_i, int *eq_j, int *ineq_j)
1096 {
1097 int k;
1098 int changed = 0;
1099 struct isl_wraps wraps;
1100 isl_mat *mat;
1101 struct isl_set *set_i = NULL;
1102 struct isl_set *set_j = NULL;
1103 struct isl_vec *bound = NULL;
1104 unsigned total = isl_basic_map_total_dim(map->p[i]);
1105  
1106 if (count(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_EQ) != 1)
1107 return 0;
1108  
1109 for (k = 0; k < 2 * map->p[i]->n_eq ; ++k)
1110 if (eq_i[k] == STATUS_ADJ_EQ)
1111 break;
1112  
1113 set_i = set_from_updated_bmap(map->p[i], tabs[i]);
1114 set_j = set_from_updated_bmap(map->p[j], tabs[j]);
1115 mat = isl_mat_alloc(map->ctx, 2 * (map->p[i]->n_eq + map->p[j]->n_eq) +
1116 map->p[i]->n_ineq + map->p[j]->n_ineq,
1117 1 + total);
1118 wraps_init(&wraps, mat, map, i, j, eq_i, ineq_i, eq_j, ineq_j);
1119 bound = isl_vec_alloc(map->ctx, 1 + total);
1120 if (!set_i || !set_j || !wraps.mat || !bound)
1121 goto error;
1122  
1123 if (k % 2 == 0)
1124 isl_seq_neg(bound->el, map->p[i]->eq[k / 2], 1 + total);
1125 else
1126 isl_seq_cpy(bound->el, map->p[i]->eq[k / 2], 1 + total);
1127 isl_int_add_ui(bound->el[0], bound->el[0], 1);
1128  
1129 isl_seq_cpy(wraps.mat->row[0], bound->el, 1 + total);
1130 wraps.mat->n_row = 1;
1131  
1132 if (add_wraps(&wraps, map->p[j], tabs[j], bound->el, set_i) < 0)
1133 goto error;
1134 if (!wraps.mat->n_row)
1135 goto unbounded;
1136  
1137 isl_int_sub_ui(bound->el[0], bound->el[0], 1);
1138 isl_seq_neg(bound->el, bound->el, 1 + total);
1139  
1140 isl_seq_cpy(wraps.mat->row[wraps.mat->n_row], bound->el, 1 + total);
1141 wraps.mat->n_row++;
1142  
1143 if (add_wraps(&wraps, map->p[i], tabs[i], bound->el, set_j) < 0)
1144 goto error;
1145 if (!wraps.mat->n_row)
1146 goto unbounded;
1147  
1148 changed = fuse(map, i, j, tabs, eq_i, ineq_i, eq_j, ineq_j, wraps.mat);
1149  
1150 if (0) {
1151 error: changed = -1;
1152 }
1153 unbounded:
1154  
1155 wraps_free(&wraps);
1156 isl_set_free(set_i);
1157 isl_set_free(set_j);
1158 isl_vec_free(bound);
1159  
1160 return changed;
1161 }
1162  
1163 /* Check if the union of the given pair of basic maps
1164 * can be represented by a single basic map.
1165 * If so, replace the pair by the single basic map and return 1.
1166 * Otherwise, return 0;
1167 * The two basic maps are assumed to live in the same local space.
1168 *
1169 * We first check the effect of each constraint of one basic map
1170 * on the other basic map.
1171 * The constraint may be
1172 * redundant the constraint is redundant in its own
1173 * basic map and should be ignore and removed
1174 * in the end
1175 * valid all (integer) points of the other basic map
1176 * satisfy the constraint
1177 * separate no (integer) point of the other basic map
1178 * satisfies the constraint
1179 * cut some but not all points of the other basic map
1180 * satisfy the constraint
1181 * adj_eq the given constraint is adjacent (on the outside)
1182 * to an equality of the other basic map
1183 * adj_ineq the given constraint is adjacent (on the outside)
1184 * to an inequality of the other basic map
1185 *
1186 * We consider seven cases in which we can replace the pair by a single
1187 * basic map. We ignore all "redundant" constraints.
1188 *
1189 * 1. all constraints of one basic map are valid
1190 * => the other basic map is a subset and can be removed
1191 *
1192 * 2. all constraints of both basic maps are either "valid" or "cut"
1193 * and the facets corresponding to the "cut" constraints
1194 * of one of the basic maps lies entirely inside the other basic map
1195 * => the pair can be replaced by a basic map consisting
1196 * of the valid constraints in both basic maps
1197 *
1198 * 3. there is a single pair of adjacent inequalities
1199 * (all other constraints are "valid")
1200 * => the pair can be replaced by a basic map consisting
1201 * of the valid constraints in both basic maps
1202 *
1203 * 4. there is a single adjacent pair of an inequality and an equality,
1204 * the other constraints of the basic map containing the inequality are
1205 * "valid". Moreover, if the inequality the basic map is relaxed
1206 * and then turned into an equality, then resulting facet lies
1207 * entirely inside the other basic map
1208 * => the pair can be replaced by the basic map containing
1209 * the inequality, with the inequality relaxed.
1210 *
1211 * 5. there is a single adjacent pair of an inequality and an equality,
1212 * the other constraints of the basic map containing the inequality are
1213 * "valid". Moreover, the facets corresponding to both
1214 * the inequality and the equality can be wrapped around their
1215 * ridges to include the other basic map
1216 * => the pair can be replaced by a basic map consisting
1217 * of the valid constraints in both basic maps together
1218 * with all wrapping constraints
1219 *
1220 * 6. one of the basic maps extends beyond the other by at most one.
1221 * Moreover, the facets corresponding to the cut constraints and
1222 * the pieces of the other basic map at offset one from these cut
1223 * constraints can be wrapped around their ridges to include
1224 * the union of the two basic maps
1225 * => the pair can be replaced by a basic map consisting
1226 * of the valid constraints in both basic maps together
1227 * with all wrapping constraints
1228 *
1229 * 7. the two basic maps live in adjacent hyperplanes. In principle
1230 * such sets can always be combined through wrapping, but we impose
1231 * that there is only one such pair, to avoid overeager coalescing.
1232 *
1233 * Throughout the computation, we maintain a collection of tableaus
1234 * corresponding to the basic maps. When the basic maps are dropped
1235 * or combined, the tableaus are modified accordingly.
1236 */
1237 static int coalesce_local_pair(__isl_keep isl_map *map, int i, int j,
1238 struct isl_tab **tabs)
1239 {
1240 int changed = 0;
1241 int *eq_i = NULL;
1242 int *eq_j = NULL;
1243 int *ineq_i = NULL;
1244 int *ineq_j = NULL;
1245  
1246 eq_i = eq_status_in(map->p[i], tabs[j]);
1247 if (!eq_i)
1248 goto error;
1249 if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ERROR))
1250 goto error;
1251 if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_SEPARATE))
1252 goto done;
1253  
1254 eq_j = eq_status_in(map->p[j], tabs[i]);
1255 if (!eq_j)
1256 goto error;
1257 if (any(eq_j, 2 * map->p[j]->n_eq, STATUS_ERROR))
1258 goto error;
1259 if (any(eq_j, 2 * map->p[j]->n_eq, STATUS_SEPARATE))
1260 goto done;
1261  
1262 ineq_i = ineq_status_in(map->p[i], tabs[i], tabs[j]);
1263 if (!ineq_i)
1264 goto error;
1265 if (any(ineq_i, map->p[i]->n_ineq, STATUS_ERROR))
1266 goto error;
1267 if (any(ineq_i, map->p[i]->n_ineq, STATUS_SEPARATE))
1268 goto done;
1269  
1270 ineq_j = ineq_status_in(map->p[j], tabs[j], tabs[i]);
1271 if (!ineq_j)
1272 goto error;
1273 if (any(ineq_j, map->p[j]->n_ineq, STATUS_ERROR))
1274 goto error;
1275 if (any(ineq_j, map->p[j]->n_ineq, STATUS_SEPARATE))
1276 goto done;
1277  
1278 if (all(eq_i, 2 * map->p[i]->n_eq, STATUS_VALID) &&
1279 all(ineq_i, map->p[i]->n_ineq, STATUS_VALID)) {
1280 drop(map, j, tabs);
1281 changed = 1;
1282 } else if (all(eq_j, 2 * map->p[j]->n_eq, STATUS_VALID) &&
1283 all(ineq_j, map->p[j]->n_ineq, STATUS_VALID)) {
1284 drop(map, i, tabs);
1285 changed = 1;
1286 } else if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_EQ)) {
1287 changed = check_eq_adj_eq(map, i, j, tabs,
1288 eq_i, ineq_i, eq_j, ineq_j);
1289 } else if (any(eq_j, 2 * map->p[j]->n_eq, STATUS_ADJ_EQ)) {
1290 changed = check_eq_adj_eq(map, j, i, tabs,
1291 eq_j, ineq_j, eq_i, ineq_i);
1292 } else if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_INEQ) ||
1293 any(eq_j, 2 * map->p[j]->n_eq, STATUS_ADJ_INEQ)) {
1294 changed = check_adj_eq(map, i, j, tabs,
1295 eq_i, ineq_i, eq_j, ineq_j);
1296 } else if (any(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_EQ) ||
1297 any(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_EQ)) {
1298 /* Can't happen */
1299 /* BAD ADJ INEQ */
1300 } else if (any(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_INEQ) ||
1301 any(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_INEQ)) {
1302 if (!any(eq_i, 2 * map->p[i]->n_eq, STATUS_CUT) &&
1303 !any(eq_j, 2 * map->p[j]->n_eq, STATUS_CUT))
1304 changed = check_adj_ineq(map, i, j, tabs,
1305 ineq_i, ineq_j);
1306 } else {
1307 if (!any(eq_i, 2 * map->p[i]->n_eq, STATUS_CUT) &&
1308 !any(eq_j, 2 * map->p[j]->n_eq, STATUS_CUT))
1309 changed = check_facets(map, i, j, tabs, ineq_i, ineq_j);
1310 if (!changed)
1311 changed = check_wrap(map, i, j, tabs,
1312 eq_i, ineq_i, eq_j, ineq_j);
1313 }
1314  
1315 done:
1316 free(eq_i);
1317 free(eq_j);
1318 free(ineq_i);
1319 free(ineq_j);
1320 return changed;
1321 error:
1322 free(eq_i);
1323 free(eq_j);
1324 free(ineq_i);
1325 free(ineq_j);
1326 return -1;
1327 }
1328  
1329 /* Do the two basic maps live in the same local space, i.e.,
1330 * do they have the same (known) divs?
1331 * If either basic map has any unknown divs, then we can only assume
1332 * that they do not live in the same local space.
1333 */
1334 static int same_divs(__isl_keep isl_basic_map *bmap1,
1335 __isl_keep isl_basic_map *bmap2)
1336 {
1337 int i;
1338 int known;
1339 int total;
1340  
1341 if (!bmap1 || !bmap2)
1342 return -1;
1343 if (bmap1->n_div != bmap2->n_div)
1344 return 0;
1345  
1346 if (bmap1->n_div == 0)
1347 return 1;
1348  
1349 known = isl_basic_map_divs_known(bmap1);
1350 if (known < 0 || !known)
1351 return known;
1352 known = isl_basic_map_divs_known(bmap2);
1353 if (known < 0 || !known)
1354 return known;
1355  
1356 total = isl_basic_map_total_dim(bmap1);
1357 for (i = 0; i < bmap1->n_div; ++i)
1358 if (!isl_seq_eq(bmap1->div[i], bmap2->div[i], 2 + total))
1359 return 0;
1360  
1361 return 1;
1362 }
1363  
1364 /* Given two basic maps "i" and "j", where the divs of "i" form a subset
1365 * of those of "j", check if basic map "j" is a subset of basic map "i"
1366 * and, if so, drop basic map "j".
1367 *
1368 * We first expand the divs of basic map "i" to match those of basic map "j",
1369 * using the divs and expansion computed by the caller.
1370 * Then we check if all constraints of the expanded "i" are valid for "j".
1371 */
1372 static int coalesce_subset(__isl_keep isl_map *map, int i, int j,
1373 struct isl_tab **tabs, __isl_keep isl_mat *div, int *exp)
1374 {
1375 isl_basic_map *bmap;
1376 int changed = 0;
1377 int *eq_i = NULL;
1378 int *ineq_i = NULL;
1379  
1380 bmap = isl_basic_map_copy(map->p[i]);
1381 bmap = isl_basic_set_expand_divs(bmap, isl_mat_copy(div), exp);
1382  
1383 if (!bmap)
1384 goto error;
1385  
1386 eq_i = eq_status_in(bmap, tabs[j]);
1387 if (!eq_i)
1388 goto error;
1389 if (any(eq_i, 2 * bmap->n_eq, STATUS_ERROR))
1390 goto error;
1391 if (any(eq_i, 2 * bmap->n_eq, STATUS_SEPARATE))
1392 goto done;
1393  
1394 ineq_i = ineq_status_in(bmap, NULL, tabs[j]);
1395 if (!ineq_i)
1396 goto error;
1397 if (any(ineq_i, bmap->n_ineq, STATUS_ERROR))
1398 goto error;
1399 if (any(ineq_i, bmap->n_ineq, STATUS_SEPARATE))
1400 goto done;
1401  
1402 if (all(eq_i, 2 * map->p[i]->n_eq, STATUS_VALID) &&
1403 all(ineq_i, map->p[i]->n_ineq, STATUS_VALID)) {
1404 drop(map, j, tabs);
1405 changed = 1;
1406 }
1407  
1408 done:
1409 isl_basic_map_free(bmap);
1410 free(eq_i);
1411 free(ineq_i);
1412 return 0;
1413 error:
1414 isl_basic_map_free(bmap);
1415 free(eq_i);
1416 free(ineq_i);
1417 return -1;
1418 }
1419  
1420 /* Check if the basic map "j" is a subset of basic map "i",
1421 * assuming that "i" has fewer divs that "j".
1422 * If not, then we change the order.
1423 *
1424 * If the two basic maps have the same number of divs, then
1425 * they must necessarily be different. Otherwise, we would have
1426 * called coalesce_local_pair. We therefore don't do try anyhing
1427 * in this case.
1428 *
1429 * We first check if the divs of "i" are all known and form a subset
1430 * of those of "j". If so, we pass control over to coalesce_subset.
1431 */
1432 static int check_coalesce_subset(__isl_keep isl_map *map, int i, int j,
1433 struct isl_tab **tabs)
1434 {
1435 int known;
1436 isl_mat *div_i, *div_j, *div;
1437 int *exp1 = NULL;
1438 int *exp2 = NULL;
1439 isl_ctx *ctx;
1440 int subset;
1441  
1442 if (map->p[i]->n_div == map->p[j]->n_div)
1443 return 0;
1444 if (map->p[j]->n_div < map->p[i]->n_div)
1445 return check_coalesce_subset(map, j, i, tabs);
1446  
1447 known = isl_basic_map_divs_known(map->p[i]);
1448 if (known < 0 || !known)
1449 return known;
1450  
1451 ctx = isl_map_get_ctx(map);
1452  
1453 div_i = isl_basic_map_get_divs(map->p[i]);
1454 div_j = isl_basic_map_get_divs(map->p[j]);
1455  
1456 if (!div_i || !div_j)
1457 goto error;
1458  
1459 exp1 = isl_alloc_array(ctx, int, div_i->n_row);
1460 exp2 = isl_alloc_array(ctx, int, div_j->n_row);
1461 if (!exp1 || !exp2)
1462 goto error;
1463  
1464 div = isl_merge_divs(div_i, div_j, exp1, exp2);
1465 if (!div)
1466 goto error;
1467  
1468 if (div->n_row == div_j->n_row)
1469 subset = coalesce_subset(map, i, j, tabs, div, exp1);
1470 else
1471 subset = 0;
1472  
1473 isl_mat_free(div);
1474  
1475 isl_mat_free(div_i);
1476 isl_mat_free(div_j);
1477  
1478 free(exp2);
1479 free(exp1);
1480  
1481 return subset;
1482 error:
1483 isl_mat_free(div_i);
1484 isl_mat_free(div_j);
1485 free(exp1);
1486 free(exp2);
1487 return -1;
1488 }
1489  
1490 /* Check if the union of the given pair of basic maps
1491 * can be represented by a single basic map.
1492 * If so, replace the pair by the single basic map and return 1.
1493 * Otherwise, return 0;
1494 *
1495 * We first check if the two basic maps live in the same local space.
1496 * If so, we do the complete check. Otherwise, we check if one is
1497 * an obvious subset of the other.
1498 */
1499 static int coalesce_pair(__isl_keep isl_map *map, int i, int j,
1500 struct isl_tab **tabs)
1501 {
1502 int same;
1503  
1504 same = same_divs(map->p[i], map->p[j]);
1505 if (same < 0)
1506 return -1;
1507 if (same)
1508 return coalesce_local_pair(map, i, j, tabs);
1509  
1510 return check_coalesce_subset(map, i, j, tabs);
1511 }
1512  
1513 static struct isl_map *coalesce(struct isl_map *map, struct isl_tab **tabs)
1514 {
1515 int i, j;
1516  
1517 for (i = map->n - 2; i >= 0; --i)
1518 restart:
1519 for (j = i + 1; j < map->n; ++j) {
1520 int changed;
1521 changed = coalesce_pair(map, i, j, tabs);
1522 if (changed < 0)
1523 goto error;
1524 if (changed)
1525 goto restart;
1526 }
1527 return map;
1528 error:
1529 isl_map_free(map);
1530 return NULL;
1531 }
1532  
1533 /* For each pair of basic maps in the map, check if the union of the two
1534 * can be represented by a single basic map.
1535 * If so, replace the pair by the single basic map and start over.
1536 */
1537 struct isl_map *isl_map_coalesce(struct isl_map *map)
1538 {
1539 int i;
1540 unsigned n;
1541 struct isl_tab **tabs = NULL;
1542  
1543 map = isl_map_remove_empty_parts(map);
1544 if (!map)
1545 return NULL;
1546  
1547 if (map->n <= 1)
1548 return map;
1549  
1550 map = isl_map_sort_divs(map);
1551 map = isl_map_cow(map);
1552  
1553 tabs = isl_calloc_array(map->ctx, struct isl_tab *, map->n);
1554 if (!tabs)
1555 goto error;
1556  
1557 n = map->n;
1558 for (i = 0; i < map->n; ++i) {
1559 tabs[i] = isl_tab_from_basic_map(map->p[i], 0);
1560 if (!tabs[i])
1561 goto error;
1562 if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_NO_IMPLICIT))
1563 if (isl_tab_detect_implicit_equalities(tabs[i]) < 0)
1564 goto error;
1565 if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_NO_REDUNDANT))
1566 if (isl_tab_detect_redundant(tabs[i]) < 0)
1567 goto error;
1568 }
1569 for (i = map->n - 1; i >= 0; --i)
1570 if (tabs[i]->empty)
1571 drop(map, i, tabs);
1572  
1573 map = coalesce(map, tabs);
1574  
1575 if (map)
1576 for (i = 0; i < map->n; ++i) {
1577 map->p[i] = isl_basic_map_update_from_tab(map->p[i],
1578 tabs[i]);
1579 map->p[i] = isl_basic_map_finalize(map->p[i]);
1580 if (!map->p[i])
1581 goto error;
1582 ISL_F_SET(map->p[i], ISL_BASIC_MAP_NO_IMPLICIT);
1583 ISL_F_SET(map->p[i], ISL_BASIC_MAP_NO_REDUNDANT);
1584 }
1585  
1586 for (i = 0; i < n; ++i)
1587 isl_tab_free(tabs[i]);
1588  
1589 free(tabs);
1590  
1591 return map;
1592 error:
1593 if (tabs)
1594 for (i = 0; i < n; ++i)
1595 isl_tab_free(tabs[i]);
1596 free(tabs);
1597 isl_map_free(map);
1598 return NULL;
1599 }
1600  
1601 /* For each pair of basic sets in the set, check if the union of the two
1602 * can be represented by a single basic set.
1603 * If so, replace the pair by the single basic set and start over.
1604 */
1605 struct isl_set *isl_set_coalesce(struct isl_set *set)
1606 {
1607 return (struct isl_set *)isl_map_coalesce((struct isl_map *)set);
1608 }