isl_coalesce.c

   1 #include "isl_map_private.h"
   2 #include "isl_tab.h"
   3
   4 #define STATUS_ERROR            -1
   5 #define STATUS_REDUNDANT         1
   6 #define STATUS_VALID             2
   7 #define STATUS_SEPARATE          3
   8 #define STATUS_CUT               4
   9 #define STATUS_ADJ_EQ            5
  10 #define STATUS_ADJ_INEQ          6
  11
  12 static int status_in(isl_int *ineq, struct isl_tab *tab)
  13 {
  14         enum isl_ineq_type type = isl_tab_ineq_type(tab, ineq);
  15         switch (type) {
  16         case isl_ineq_error:            return STATUS_ERROR;
  17         case isl_ineq_redundant:        return STATUS_VALID;
  18         case isl_ineq_separate:         return STATUS_SEPARATE;
  19         case isl_ineq_cut:              return STATUS_CUT;
  20         case isl_ineq_adj_eq:           return STATUS_ADJ_EQ;
  21         case isl_ineq_adj_ineq:         return STATUS_ADJ_INEQ;
  22         }
  23 }
  24
  25 /* Compute the position of the equalities of basic map "i"
  26  * with respect to basic map "j".
  27  * The resulting array has twice as many entries as the number
  28  * of equalities corresponding to the two inequalties to which
  29  * each equality corresponds.
  30  */
  31 static int *eq_status_in(struct isl_map *map, int i, int j,
  32         struct isl_tab **tabs)
  33 {
  34         int k, l;
  35         int *eq = isl_calloc_array(map->ctx, int, 2 * map->p[i]->n_eq);
  36         unsigned dim;
  37
  38         dim = isl_basic_map_total_dim(map->p[i]);
  39         for (k = 0; k < map->p[i]->n_eq; ++k) {
  40                 for (l = 0; l < 2; ++l) {
  41                         isl_seq_neg(map->p[i]->eq[k], map->p[i]->eq[k], 1+dim);
  42                         eq[2 * k + l] = status_in(map->p[i]->eq[k], tabs[j]);
  43                         if (eq[2 * k + l] == STATUS_ERROR)
  44                                 goto error;
  45                 }
  46                 if (eq[2 * k] == STATUS_SEPARATE ||
  47                     eq[2 * k + 1] == STATUS_SEPARATE)
  48                         break;
  49         }
  50
  51         return eq;
  52 error:
  53         free(eq);
  54         return NULL;
  55 }
  56
  57 /* Compute the position of the inequalities of basic map "i"
  58  * with respect to basic map "j".
  59  */
  60 static int *ineq_status_in(struct isl_map *map, int i, int j,
  61         struct isl_tab **tabs)
  62 {
  63         int k;
  64         unsigned n_eq = map->p[i]->n_eq;
  65         int *ineq = isl_calloc_array(map->ctx, int, map->p[i]->n_ineq);
  66
  67         for (k = 0; k < map->p[i]->n_ineq; ++k) {
  68                 if (isl_tab_is_redundant(tabs[i], n_eq + k)) {
  69                         ineq[k] = STATUS_REDUNDANT;
  70                         continue;
  71                 }
  72                 ineq[k] = status_in(map->p[i]->ineq[k], tabs[j]);
  73                 if (ineq[k] == STATUS_ERROR)
  74                         goto error;
  75                 if (ineq[k] == STATUS_SEPARATE)
  76                         break;
  77         }
  78
  79         return ineq;
  80 error:
  81         free(ineq);
  82         return NULL;
  83 }
  84
  85 static int any(int *con, unsigned len, int status)
  86 {
  87         int i;
  88
  89         for (i = 0; i < len ; ++i)
  90                 if (con[i] == status)
  91                         return 1;
  92         return 0;
  93 }
  94
  95 static int count(int *con, unsigned len, int status)
  96 {
  97         int i;
  98         int c = 0;
  99
 100         for (i = 0; i < len ; ++i)
 101                 if (con[i] == status)
 102                         c++;
 103         return c;
 104 }
 105
 106 static int all(int *con, unsigned len, int status)
 107 {
 108         int i;
 109
 110         for (i = 0; i < len ; ++i) {
 111                 if (con[i] == STATUS_REDUNDANT)
 112                         continue;
 113                 if (con[i] != status)
 114                         return 0;
 115         }
 116         return 1;
 117 }
 118
 119 static void drop(struct isl_map *map, int i, struct isl_tab **tabs)
 120 {
 121         isl_basic_map_free(map->p[i]);
 122         isl_tab_free(tabs[i]);
 123
 124         if (i != map->n - 1) {
 125                 map->p[i] = map->p[map->n - 1];
 126                 tabs[i] = tabs[map->n - 1];
 127         }
 128         tabs[map->n - 1] = NULL;
 129         map->n--;
 130 }
 131
 132 /* Replace the pair of basic maps i and j but the basic map bounded
 133  * by the valid constraints in both basic maps.
 134  */
 135 static int fuse(struct isl_map *map, int i, int j, struct isl_tab **tabs,
 136         int *ineq_i, int *ineq_j)
 137 {
 138         int k, l;
 139         struct isl_basic_map *fused = NULL;
 140         struct isl_tab *fused_tab = NULL;
 141         unsigned total = isl_basic_map_total_dim(map->p[i]);
 142
 143         fused = isl_basic_map_alloc_dim(isl_dim_copy(map->p[i]->dim),
 144                         map->p[i]->n_div,
 145                         map->p[i]->n_eq + map->p[j]->n_eq,
 146                         map->p[i]->n_ineq + map->p[j]->n_ineq);
 147         if (!fused)
 148                 goto error;
 149
 150         for (k = 0; k < map->p[i]->n_eq; ++k) {
 151                 int l = isl_basic_map_alloc_equality(fused);
 152                 isl_seq_cpy(fused->eq[l], map->p[i]->eq[k], 1 + total);
 153         }
 154
 155         for (k = 0; k < map->p[j]->n_eq; ++k) {
 156                 int l = isl_basic_map_alloc_equality(fused);
 157                 isl_seq_cpy(fused->eq[l], map->p[j]->eq[k], 1 + total);
 158         }
 159
 160         for (k = 0; k < map->p[i]->n_ineq; ++k) {
 161                 if (ineq_i[k] != STATUS_VALID)
 162                         continue;
 163                 l = isl_basic_map_alloc_inequality(fused);
 164                 isl_seq_cpy(fused->ineq[l], map->p[i]->ineq[k], 1 + total);
 165         }
 166
 167         for (k = 0; k < map->p[j]->n_ineq; ++k) {
 168                 if (ineq_j[k] != STATUS_VALID)
 169                         continue;
 170                 l = isl_basic_map_alloc_inequality(fused);
 171                 isl_seq_cpy(fused->ineq[l], map->p[j]->ineq[k], 1 + total);
 172         }
 173
 174         for (k = 0; k < map->p[i]->n_div; ++k) {
 175                 int l = isl_basic_map_alloc_div(fused);
 176                 isl_seq_cpy(fused->div[l], map->p[i]->div[k], 1 + 1 + total);
 177         }
 178
 179         fused = isl_basic_map_gauss(fused, NULL);
 180         ISL_F_SET(fused, ISL_BASIC_MAP_FINAL);
 181
 182         fused_tab = isl_tab_from_basic_map(fused);
 183         fused_tab = isl_tab_detect_redundant(fused_tab);
 184         if (!fused_tab)
 185                 goto error;
 186
 187         isl_basic_map_free(map->p[i]);
 188         map->p[i] = fused;
 189         isl_tab_free(tabs[i]);
 190         tabs[i] = fused_tab;
 191         drop(map, j, tabs);
 192
 193         return 1;
 194 error:
 195         isl_basic_map_free(fused);
 196         return -1;
 197 }
 198
 199 /* Given a pair of basic maps i and j such that all constraints are either
 200  * "valid" or "cut", check if the facets corresponding to the "cut"
 201  * constraints of i lie entirely within basic map j.
 202  * If so, replace the pair by the basic map consisting of the valid
 203  * constraints in both basic maps.
 204  *
 205  * To see that we are not introducing any extra points, call the
 206  * two basic maps A and B and the resulting map U and let x
 207  * be an element of U \setminus ( A \cup B ).
 208  * Then there is a pair of cut constraints c_1 and c_2 in A and B such that x
 209  * violates them.  Let X be the intersection of U with the opposites
 210  * of these constraints.  Then x \in X.
 211  * The facet corresponding to c_1 contains the corresponding facet of A.
 212  * This facet is entirely contained in B, so c_2 is valid on the facet.
 213  * However, since it is also (part of) a facet of X, -c_2 is also valid
 214  * on the facet.  This means c_2 is saturated on the facet, so c_1 and
 215  * c_2 must be opposites of each other, but then x could not violate
 216  * both of them.
 217  */
 218 static int check_facets(struct isl_map *map, int i, int j,
 219         struct isl_tab **tabs, int *ineq_i, int *ineq_j)
 220 {
 221         int k, l;
 222         struct isl_tab_undo *snap;
 223         unsigned n_eq = map->p[i]->n_eq;
 224
 225         snap = isl_tab_snap(tabs[i]);
 226
 227         for (k = 0; k < map->p[i]->n_ineq; ++k) {
 228                 if (ineq_i[k] != STATUS_CUT)
 229                         continue;
 230                 tabs[i] = isl_tab_select_facet(tabs[i], n_eq + k);
 231                 for (l = 0; l < map->p[j]->n_ineq; ++l) {
 232                         int stat;
 233                         if (ineq_j[l] != STATUS_CUT)
 234                                 continue;
 235                         stat = status_in(map->p[j]->ineq[l], tabs[i]);
 236                         if (stat != STATUS_VALID)
 237                                 break;
 238                 }
 239                 isl_tab_rollback(tabs[i], snap);
 240                 if (l < map->p[j]->n_ineq)
 241                         break;
 242         }
 243
 244         if (k < map->p[i]->n_ineq)
 245                 /* BAD CUT PAIR */
 246                 return 0;
 247         return fuse(map, i, j, tabs, ineq_i, ineq_j);
 248 }
 249
 250 /* Both basic maps have at least one inequality with and adjacent
 251  * (but opposite) inequality in the other basic map.
 252  * Check that there are no cut constraints and that there is only
 253  * a single pair of adjacent inequalities.
 254  * If so, we can replace the pair by a single basic map described
 255  * by all but the pair of adjacent inequalities.
 256  * Any additional points introduced lie strictly between the two
 257  * adjacent hyperplanes and can therefore be integral.
 258  *
 259  *        ____                    _____
 260  *       /    ||\                /     \
 261  *      /     || \              /       \
 262  *      \     ||  \     =>      \        \
 263  *       \    ||  /              \       /
 264  *        \___||_/                \_____/
 265  *
 266  * The test for a single pair of adjancent inequalities is important
 267  * for avoiding the combination of two basic maps like the following
 268  *
 269  *       /|
 270  *      / |
 271  *     /__|
 272  *         _____
 273  *         |   |
 274  *         |   |
 275  *         |___|
 276  */
 277 static int check_adj_ineq(struct isl_map *map, int i, int j,
 278         struct isl_tab **tabs, int *ineq_i, int *ineq_j)
 279 {
 280         int changed = 0;
 281
 282         if (any(ineq_i, map->p[i]->n_ineq, STATUS_CUT) ||
 283             any(ineq_j, map->p[j]->n_ineq, STATUS_CUT))
 284                 /* ADJ INEQ CUT */
 285                 ;
 286         else if (count(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_INEQ) == 1 &&
 287                  count(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_INEQ) == 1)
 288                 changed = fuse(map, i, j, tabs, ineq_i, ineq_j);
 289         /* else ADJ INEQ TOO MANY */
 290
 291         return changed;
 292 }
 293
 294 /* Check if basic map "i" contains the basic map represented
 295  * by the tableau "tab".
 296  */
 297 static int contains(struct isl_map *map, int i, int *ineq_i,
 298         struct isl_tab *tab)
 299 {
 300         int k, l;
 301         unsigned dim;
 302
 303         dim = isl_basic_map_total_dim(map->p[i]);
 304         for (k = 0; k < map->p[i]->n_eq; ++k) {
 305                 for (l = 0; l < 2; ++l) {
 306                         int stat;
 307                         isl_seq_neg(map->p[i]->eq[k], map->p[i]->eq[k], 1+dim);
 308                         stat = status_in(map->p[i]->eq[k], tab);
 309                         if (stat != STATUS_VALID)
 310                                 return 0;
 311                 }
 312         }
 313
 314         for (k = 0; k < map->p[i]->n_ineq; ++k) {
 315                 int stat;
 316                 if (ineq_i[k] == STATUS_REDUNDANT)
 317                         continue;
 318                 stat = status_in(map->p[i]->ineq[k], tab);
 319                 if (stat != STATUS_VALID)
 320                         return 0;
 321         }
 322         return 1;
 323 }
 324
 325 /* At least one of the basic maps has an equality that is adjacent
 326  * to inequality.  Make sure that only one of the basic maps has
 327  * such an equality and that the other basic map has exactly one
 328  * inequality adjacent to an equality.
 329  * We call the basic map that has the inequality "i" and the basic
 330  * map that has the equality "j".
 331  * If "i" has any "cut" inequality, then relaxing the inequality
 332  * by one would not result in a basic map that contains the other
 333  * basic map.
 334  * Otherwise, we relax the constraint, compute the corresponding
 335  * facet and check whether it is included in the other basic map.
 336  * If so, we know that relaxing the constraint extend the basic
 337  * map with exactly the other basic map (we already know that this
 338  * other basic map is included in the extension, because there
 339  * were no "cut" inequalities in "i") and we can replace the
 340  * two basic maps by thie extension.
 341  *        ____                    _____
 342  *       /    ||                 /     |
 343  *      /     ||                /      |
 344  *      \     ||        =>      \      |
 345  *       \    ||                 \     |
 346  *        \___||                  \____|
 347  */
 348 static int check_adj_eq(struct isl_map *map, int i, int j,
 349         struct isl_tab **tabs, int *eq_i, int *ineq_i, int *eq_j, int *ineq_j)
 350 {
 351         int changed = 0;
 352         int super;
 353         int k;
 354         struct isl_tab_undo *snap, *snap2;
 355         unsigned n_eq = map->p[i]->n_eq;
 356
 357         if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_INEQ) &&
 358             any(eq_j, 2 * map->p[j]->n_eq, STATUS_ADJ_INEQ))
 359                 /* ADJ EQ TOO MANY */
 360                 return 0;
 361
 362         if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_INEQ))
 363                 return check_adj_eq(map, j, i, tabs,
 364                                         eq_j, ineq_j, eq_i, ineq_i);
 365
 366         /* j has an equality adjacent to an inequality in i */
 367
 368         if (any(ineq_i, map->p[i]->n_ineq, STATUS_CUT))
 369                 /* ADJ EQ CUT */
 370                 return 0;
 371         if (count(eq_j, 2 * map->p[j]->n_eq, STATUS_ADJ_INEQ) != 1 ||
 372             count(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_EQ) != 1 ||
 373             any(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_EQ) ||
 374             any(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_INEQ) ||
 375             any(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_INEQ))
 376                 /* ADJ EQ TOO MANY */
 377                 return 0;
 378
 379         for (k = 0; k < map->p[i]->n_ineq ; ++k)
 380                 if (ineq_i[k] == STATUS_ADJ_EQ)
 381                         break;
 382
 383         snap = isl_tab_snap(tabs[i]);
 384         tabs[i] = isl_tab_relax(tabs[i], n_eq + k);
 385         snap2 = isl_tab_snap(tabs[i]);
 386         tabs[i] = isl_tab_select_facet(tabs[i], n_eq + k);
 387         super = contains(map, j, ineq_j, tabs[i]);
 388         if (super) {
 389                 isl_tab_rollback(tabs[i], snap2);
 390                 map->p[i] = isl_basic_map_cow(map->p[i]);
 391                 if (!map->p[i])
 392                         return -1;
 393                 isl_int_add_ui(map->p[i]->ineq[k][0], map->p[i]->ineq[k][0], 1);
 394                 ISL_F_SET(map->p[i], ISL_BASIC_MAP_FINAL);
 395                 drop(map, j, tabs);
 396                 changed = 1;
 397         } else
 398                 isl_tab_rollback(tabs[i], snap);
 399
 400         return changed;
 401 }
 402
 403 /* Check if the union of the given pair of basic maps
 404  * can be represented by a single basic map.
 405  * If so, replace the pair by the single basic map and return 1.
 406  * Otherwise, return 0;
 407  *
 408  * We first check the effect of each constraint of one basic map
 409  * on the other basic map.
 410  * The constraint may be
 411  *      redundant       the constraint is redundant in its own
 412  *                      basic map and should be ignore and removed
 413  *                      in the end
 414  *      valid           all (integer) points of the other basic map
 415  *                      satisfy the constraint
 416  *      separate        no (integer) point of the other basic map
 417  *                      satisfies the constraint
 418  *      cut             some but not all points of the other basic map
 419  *                      satisfy the constraint
 420  *      adj_eq          the given constraint is adjacent (on the outside)
 421  *                      to an equality of the other basic map
 422  *      adj_ineq        the given constraint is adjacent (on the outside)
 423  *                      to an inequality of the other basic map
 424  *
 425  * We consider four cases in which we can replace the pair by a single
 426  * basic map.  We ignore all "redundant" constraints.
 427  *
 428  *      1. all constraints of one basic map are valid
 429  *              => the other basic map is a subset and can be removed
 430  *
 431  *      2. all constraints of both basic maps are either "valid" or "cut"
 432  *         and the facets corresponding to the "cut" constraints
 433  *         of one of the basic maps lies entirely inside the other basic map
 434  *              => the pair can be replaced by a basic map consisting
 435  *                 of the valid constraints in both basic maps
 436  *
 437  *      3. there is a single pair of adjacent inequalities
 438  *         (all other constraints are "valid")
 439  *              => the pair can be replaced by a basic map consisting
 440  *                 of the valid constraints in both basic maps
 441  *
 442  *      4. there is a single adjacent pair of an inequality and an equality,
 443  *         the other constraints of the basic map containing the inequality are
 444  *         "valid".  Moreover, if the inequality the basic map is relaxed
 445  *         and then turned into an equality, then resulting facet lies
 446  *         entirely inside the other basic map
 447  *              => the pair can be replaced by the basic map containing
 448  *                 the inequality, with the inequality relaxed.
 449  *
 450  * Throughout the computation, we maintain a collection of tableaus
 451  * corresponding to the basic maps.  When the basic maps are dropped
 452  * or combined, the tableaus are modified accordingly.
 453  */
 454 static int coalesce_pair(struct isl_map *map, int i, int j,
 455         struct isl_tab **tabs)
 456 {
 457         int changed = 0;
 458         int *eq_i = NULL;
 459         int *eq_j = NULL;
 460         int *ineq_i = NULL;
 461         int *ineq_j = NULL;
 462
 463         eq_i = eq_status_in(map, i, j, tabs);
 464         if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ERROR))
 465                 goto error;
 466         if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_SEPARATE))
 467                 goto done;
 468
 469         eq_j = eq_status_in(map, j, i, tabs);
 470         if (any(eq_j, 2 * map->p[j]->n_eq, STATUS_ERROR))
 471                 goto error;
 472         if (any(eq_j, 2 * map->p[j]->n_eq, STATUS_SEPARATE))
 473                 goto done;
 474
 475         ineq_i = ineq_status_in(map, i, j, tabs);
 476         if (any(ineq_i, map->p[i]->n_ineq, STATUS_ERROR))
 477                 goto error;
 478         if (any(ineq_i, map->p[i]->n_ineq, STATUS_SEPARATE))
 479                 goto done;
 480
 481         ineq_j = ineq_status_in(map, j, i, tabs);
 482         if (any(ineq_j, map->p[j]->n_ineq, STATUS_ERROR))
 483                 goto error;
 484         if (any(ineq_j, map->p[j]->n_ineq, STATUS_SEPARATE))
 485                 goto done;
 486
 487         if (all(eq_i, 2 * map->p[i]->n_eq, STATUS_VALID) &&
 488             all(ineq_i, map->p[i]->n_ineq, STATUS_VALID)) {
 489                 drop(map, j, tabs);
 490                 changed = 1;
 491         } else if (all(eq_j, 2 * map->p[j]->n_eq, STATUS_VALID) &&
 492                    all(ineq_j, map->p[j]->n_ineq, STATUS_VALID)) {
 493                 drop(map, i, tabs);
 494                 changed = 1;
 495         } else if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_CUT) ||
 496                    any(eq_j, 2 * map->p[j]->n_eq, STATUS_CUT)) {
 497                 /* BAD CUT */
 498         } else if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_EQ) ||
 499                    any(eq_j, 2 * map->p[j]->n_eq, STATUS_ADJ_EQ)) {
 500                 /* ADJ EQ PAIR */
 501         } else if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_INEQ) ||
 502                    any(eq_j, 2 * map->p[j]->n_eq, STATUS_ADJ_INEQ)) {
 503                 changed = check_adj_eq(map, i, j, tabs,
 504                                         eq_i, ineq_i, eq_j, ineq_j);
 505         } else if (any(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_EQ) ||
 506                    any(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_EQ)) {
 507                 /* Can't happen */
 508                 /* BAD ADJ INEQ */
 509         } else if (any(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_INEQ) ||
 510                    any(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_INEQ)) {
 511                 changed = check_adj_ineq(map, i, j, tabs, ineq_i, ineq_j);
 512         } else
 513                 changed = check_facets(map, i, j, tabs, ineq_i, ineq_j);
 514
 515 done:
 516         free(eq_i);
 517         free(eq_j);
 518         free(ineq_i);
 519         free(ineq_j);
 520         return changed;
 521 error:
 522         free(eq_i);
 523         free(eq_j);
 524         free(ineq_i);
 525         free(ineq_j);
 526         return -1;
 527 }
 528
 529 static struct isl_map *coalesce(struct isl_map *map, struct isl_tab **tabs)
 530 {
 531         int i, j;
 532
 533         for (i = 0; i < map->n - 1; ++i)
 534                 for (j = i + 1; j < map->n; ++j) {
 535                         int changed;
 536                         changed = coalesce_pair(map, i, j, tabs);
 537                         if (changed < 0)
 538                                 goto error;
 539                         if (changed)
 540                                 return coalesce(map, tabs);
 541                 }
 542         return map;
 543 error:
 544         isl_map_free(map);
 545         return NULL;
 546 }
 547
 548 /* For each pair of basic maps in the map, check if the union of the two
 549  * can be represented by a single basic map.
 550  * If so, replace the pair by the single basic map and start over.
 551  */
 552 struct isl_map *isl_map_coalesce(struct isl_map *map)
 553 {
 554         int i;
 555         unsigned n;
 556         struct isl_tab **tabs = NULL;
 557
 558         if (!map)
 559                 return NULL;
 560
 561         if (map->n <= 1)
 562                 return map;
 563
 564         map = isl_map_align_divs(map);
 565
 566         tabs = isl_calloc_array(map->ctx, struct isl_tab *, map->n);
 567         if (!tabs)
 568                 goto error;
 569
 570         n = map->n;
 571         for (i = 0; i < map->n; ++i) {
 572                 tabs[i] = isl_tab_from_basic_map(map->p[i]);
 573                 if (!tabs[i])
 574                         goto error;
 575                 if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_NO_IMPLICIT))
 576                         tabs[i] = isl_tab_detect_equalities(tabs[i]);
 577                 if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_NO_REDUNDANT))
 578                         tabs[i] = isl_tab_detect_redundant(tabs[i]);
 579         }
 580         for (i = map->n - 1; i >= 0; --i)
 581                 if (tabs[i]->empty)
 582                         drop(map, i, tabs);
 583
 584         map = coalesce(map, tabs);
 585
 586         if (map)
 587                 for (i = 0; i < map->n; ++i) {
 588                         map->p[i] = isl_basic_map_update_from_tab(map->p[i],
 589                                                                     tabs[i]);
 590                         map->p[i] = isl_basic_map_finalize(map->p[i]);
 591                         if (!map->p[i])
 592                                 goto error;
 593                         ISL_F_SET(map->p[i], ISL_BASIC_MAP_NO_IMPLICIT);
 594                         ISL_F_SET(map->p[i], ISL_BASIC_MAP_NO_REDUNDANT);
 595                 }
 596
 597         for (i = 0; i < n; ++i)
 598                 isl_tab_free(tabs[i]);
 599
 600         free(tabs);
 601
 602         return map;
 603 error:
 604         if (tabs)
 605                 for (i = 0; i < n; ++i)
 606                         isl_tab_free(tabs[i]);
 607         free(tabs);
 608         return NULL;
 609 }
 610
 611 /* For each pair of basic sets in the set, check if the union of the two
 612  * can be represented by a single basic set.
 613  * If so, replace the pair by the single basic set and start over.
 614  */
 615 struct isl_set *isl_set_coalesce(struct isl_set *set)
 616 {
 617         (struct isl_set *)isl_map_coalesce((struct isl_map *)set);
 618 }