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