1/* 2 * Copyright 2008-2009 Katholieke Universiteit Leuven 3 * Copyright 2010 INRIA Saclay 4 * Copyright 2012-2013 Ecole Normale Superieure 5 * 6 * Use of this software is governed by the MIT 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 30static 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 */ 50static 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; 71error: 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 */ 80static 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; 100error: 101 free(ineq); 102 return NULL; 103} 104 105static 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 115static 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 126static 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 139static 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 */ 156static 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; 242error: 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 */ 267static 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/* Check if basic map "i" contains the basic map represented 302 * by the tableau "tab". 303 */ 304static int contains(struct isl_map *map, int i, int *ineq_i, 305 struct isl_tab *tab) 306{ 307 int k, l; 308 unsigned dim; 309 310 dim = isl_basic_map_total_dim(map->p[i]); 311 for (k = 0; k < map->p[i]->n_eq; ++k) { 312 for (l = 0; l < 2; ++l) { 313 int stat; 314 isl_seq_neg(map->p[i]->eq[k], map->p[i]->eq[k], 1+dim); 315 stat = status_in(map->p[i]->eq[k], tab); 316 if (stat != STATUS_VALID) 317 return 0; 318 } 319 } 320 321 for (k = 0; k < map->p[i]->n_ineq; ++k) { 322 int stat; 323 if (ineq_i[k] == STATUS_REDUNDANT) 324 continue; 325 stat = status_in(map->p[i]->ineq[k], tab); 326 if (stat != STATUS_VALID) 327 return 0; 328 } 329 return 1; 330} 331 332/* Basic map "i" has an inequality (say "k") that is adjacent 333 * to some inequality of basic map "j". All the other inequalities 334 * are valid for "j". 335 * Check if basic map "j" forms an extension of basic map "i". 336 * 337 * Note that this function is only called if some of the equalities or 338 * inequalities of basic map "j" do cut basic map "i". The function is 339 * correct even if there are no such cut constraints, but in that case 340 * the additional checks performed by this function are overkill. 341 * 342 * In particular, we replace constraint k, say f >= 0, by constraint 343 * f <= -1, add the inequalities of "j" that are valid for "i" 344 * and check if the result is a subset of basic map "j". 345 * If so, then we know that this result is exactly equal to basic map "j" 346 * since all its constraints are valid for basic map "j". 347 * By combining the valid constraints of "i" (all equalities and all 348 * inequalities except "k") and the valid constraints of "j" we therefore 349 * obtain a basic map that is equal to their union. 350 * In this case, there is no need to perform a rollback of the tableau 351 * since it is going to be destroyed in fuse(). 352 * 353 * 354 * |\__ |\__ 355 * | \__ | \__ 356 * | \_ => | \__ 357 * |_______| _ |_________\ 358 * 359 * 360 * |\ |\ 361 * | \ | \ 362 * | \ | \ 363 * | | | \ 364 * | ||\ => | \ 365 * | || \ | \ 366 * | || | | | 367 * |__||_/ |_____/ 368 */ 369static int is_adj_ineq_extension(__isl_keep isl_map *map, int i, int j, 370 struct isl_tab **tabs, int *eq_i, int *ineq_i, int *eq_j, int *ineq_j) 371{ 372 int k; 373 struct isl_tab_undo *snap; 374 unsigned n_eq = map->p[i]->n_eq; 375 unsigned total = isl_basic_map_total_dim(map->p[i]); 376 int r; 377 378 if (isl_tab_extend_cons(tabs[i], 1 + map->p[j]->n_ineq) < 0) 379 return -1; 380 381 for (k = 0; k < map->p[i]->n_ineq; ++k) 382 if (ineq_i[k] == STATUS_ADJ_INEQ) 383 break; 384 if (k >= map->p[i]->n_ineq) 385 isl_die(isl_map_get_ctx(map), isl_error_internal, 386 "ineq_i should have exactly one STATUS_ADJ_INEQ", 387 return -1); 388 389 snap = isl_tab_snap(tabs[i]); 390 391 if (isl_tab_unrestrict(tabs[i], n_eq + k) < 0) 392 return -1; 393 394 isl_seq_neg(map->p[i]->ineq[k], map->p[i]->ineq[k], 1 + total); 395 isl_int_sub_ui(map->p[i]->ineq[k][0], map->p[i]->ineq[k][0], 1); 396 r = isl_tab_add_ineq(tabs[i], map->p[i]->ineq[k]); 397 isl_seq_neg(map->p[i]->ineq[k], map->p[i]->ineq[k], 1 + total); 398 isl_int_sub_ui(map->p[i]->ineq[k][0], map->p[i]->ineq[k][0], 1); 399 if (r < 0) 400 return -1; 401 402 for (k = 0; k < map->p[j]->n_ineq; ++k) { 403 if (ineq_j[k] != STATUS_VALID) 404 continue; 405 if (isl_tab_add_ineq(tabs[i], map->p[j]->ineq[k]) < 0) 406 return -1; 407 } 408 409 if (contains(map, j, ineq_j, tabs[i])) 410 return fuse(map, i, j, tabs, eq_i, ineq_i, eq_j, ineq_j, NULL); 411 412 if (isl_tab_rollback(tabs[i], snap) < 0) 413 return -1; 414 415 return 0; 416} 417 418 419/* Both basic maps have at least one inequality with and adjacent 420 * (but opposite) inequality in the other basic map. 421 * Check that there are no cut constraints and that there is only 422 * a single pair of adjacent inequalities. 423 * If so, we can replace the pair by a single basic map described 424 * by all but the pair of adjacent inequalities. 425 * Any additional points introduced lie strictly between the two 426 * adjacent hyperplanes and can therefore be integral. 427 * 428 * ____ _____ 429 * / ||\ / \ 430 * / || \ / \ 431 * \ || \ => \ \ 432 * \ || / \ / 433 * \___||_/ \_____/ 434 * 435 * The test for a single pair of adjancent inequalities is important 436 * for avoiding the combination of two basic maps like the following 437 * 438 * /| 439 * / | 440 * /__| 441 * _____ 442 * | | 443 * | | 444 * |___| 445 * 446 * If there are some cut constraints on one side, then we may 447 * still be able to fuse the two basic maps, but we need to perform 448 * some additional checks in is_adj_ineq_extension. 449 */ 450static int check_adj_ineq(struct isl_map *map, int i, int j, 451 struct isl_tab **tabs, int *eq_i, int *ineq_i, int *eq_j, int *ineq_j) 452{ 453 int count_i, count_j; 454 int cut_i, cut_j; 455 456 count_i = count(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_INEQ); 457 count_j = count(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_INEQ); 458 459 if (count_i != 1 && count_j != 1) 460 return 0; 461 462 cut_i = any(eq_i, 2 * map->p[i]->n_eq, STATUS_CUT) || 463 any(ineq_i, map->p[i]->n_ineq, STATUS_CUT); 464 cut_j = any(eq_j, 2 * map->p[j]->n_eq, STATUS_CUT) || 465 any(ineq_j, map->p[j]->n_ineq, STATUS_CUT); 466 467 if (!cut_i && !cut_j && count_i == 1 && count_j == 1) 468 return fuse(map, i, j, tabs, NULL, ineq_i, NULL, ineq_j, NULL); 469 470 if (count_i == 1 && !cut_i) 471 return is_adj_ineq_extension(map, i, j, tabs, 472 eq_i, ineq_i, eq_j, ineq_j); 473 474 if (count_j == 1 && !cut_j) 475 return is_adj_ineq_extension(map, j, i, tabs, 476 eq_j, ineq_j, eq_i, ineq_i); 477 478 return 0; 479} 480 481/* Basic map "i" has an inequality "k" that is adjacent to some equality 482 * of basic map "j". All the other inequalities are valid for "j". 483 * Check if basic map "j" forms an extension of basic map "i". 484 * 485 * In particular, we relax constraint "k", compute the corresponding 486 * facet and check whether it is included in the other basic map. 487 * If so, we know that relaxing the constraint extends the basic 488 * map with exactly the other basic map (we already know that this 489 * other basic map is included in the extension, because there 490 * were no "cut" inequalities in "i") and we can replace the 491 * two basic maps by this extension. 492 * ____ _____ 493 * / || / | 494 * / || / | 495 * \ || => \ | 496 * \ || \ | 497 * \___|| \____| 498 */ 499static int is_adj_eq_extension(struct isl_map *map, int i, int j, int k, 500 struct isl_tab **tabs, int *eq_i, int *ineq_i, int *eq_j, int *ineq_j) 501{ 502 int changed = 0; 503 int super; 504 struct isl_tab_undo *snap, *snap2; 505 unsigned n_eq = map->p[i]->n_eq; 506 507 if (isl_tab_is_equality(tabs[i], n_eq + k)) 508 return 0; 509 510 snap = isl_tab_snap(tabs[i]); 511 tabs[i] = isl_tab_relax(tabs[i], n_eq + k); 512 snap2 = isl_tab_snap(tabs[i]); 513 if (isl_tab_select_facet(tabs[i], n_eq + k) < 0) 514 return -1; 515 super = contains(map, j, ineq_j, tabs[i]); 516 if (super) { 517 if (isl_tab_rollback(tabs[i], snap2) < 0) 518 return -1; 519 map->p[i] = isl_basic_map_cow(map->p[i]); 520 if (!map->p[i]) 521 return -1; 522 isl_int_add_ui(map->p[i]->ineq[k][0], map->p[i]->ineq[k][0], 1); 523 ISL_F_SET(map->p[i], ISL_BASIC_MAP_FINAL); 524 drop(map, j, tabs); 525 changed = 1; 526 } else 527 if (isl_tab_rollback(tabs[i], snap) < 0) 528 return -1; 529 530 return changed; 531} 532 533/* Data structure that keeps track of the wrapping constraints 534 * and of information to bound the coefficients of those constraints. 535 * 536 * bound is set if we want to apply a bound on the coefficients 537 * mat contains the wrapping constraints 538 * max is the bound on the coefficients (if bound is set) 539 */ 540struct isl_wraps { 541 int bound; 542 isl_mat *mat; 543 isl_int max; 544}; 545 546/* Update wraps->max to be greater than or equal to the coefficients 547 * in the equalities and inequalities of bmap that can be removed if we end up 548 * applying wrapping. 549 */ 550static void wraps_update_max(struct isl_wraps *wraps, 551 __isl_keep isl_basic_map *bmap, int *eq, int *ineq) 552{ 553 int k; 554 isl_int max_k; 555 unsigned total = isl_basic_map_total_dim(bmap); 556 557 isl_int_init(max_k); 558 559 for (k = 0; k < bmap->n_eq; ++k) { 560 if (eq[2 * k] == STATUS_VALID && 561 eq[2 * k + 1] == STATUS_VALID) 562 continue; 563 isl_seq_abs_max(bmap->eq[k] + 1, total, &max_k); 564 if (isl_int_abs_gt(max_k, wraps->max)) 565 isl_int_set(wraps->max, max_k); 566 } 567 568 for (k = 0; k < bmap->n_ineq; ++k) { 569 if (ineq[k] == STATUS_VALID || ineq[k] == STATUS_REDUNDANT) 570 continue; 571 isl_seq_abs_max(bmap->ineq[k] + 1, total, &max_k); 572 if (isl_int_abs_gt(max_k, wraps->max)) 573 isl_int_set(wraps->max, max_k); 574 } 575 576 isl_int_clear(max_k); 577} 578 579/* Initialize the isl_wraps data structure. 580 * If we want to bound the coefficients of the wrapping constraints, 581 * we set wraps->max to the largest coefficient 582 * in the equalities and inequalities that can be removed if we end up 583 * applying wrapping. 584 */ 585static void wraps_init(struct isl_wraps *wraps, __isl_take isl_mat *mat, 586 __isl_keep isl_map *map, int i, int j, 587 int *eq_i, int *ineq_i, int *eq_j, int *ineq_j) 588{ 589 isl_ctx *ctx; 590 591 wraps->bound = 0; 592 wraps->mat = mat; 593 if (!mat) 594 return; 595 ctx = isl_mat_get_ctx(mat); 596 wraps->bound = isl_options_get_coalesce_bounded_wrapping(ctx); 597 if (!wraps->bound) 598 return; 599 isl_int_init(wraps->max); 600 isl_int_set_si(wraps->max, 0); 601 wraps_update_max(wraps, map->p[i], eq_i, ineq_i); 602 wraps_update_max(wraps, map->p[j], eq_j, ineq_j); 603} 604 605/* Free the contents of the isl_wraps data structure. 606 */ 607static void wraps_free(struct isl_wraps *wraps) 608{ 609 isl_mat_free(wraps->mat); 610 if (wraps->bound) 611 isl_int_clear(wraps->max); 612} 613 614/* Is the wrapping constraint in row "row" allowed? 615 * 616 * If wraps->bound is set, we check that none of the coefficients 617 * is greater than wraps->max. 618 */ 619static int allow_wrap(struct isl_wraps *wraps, int row) 620{ 621 int i; 622 623 if (!wraps->bound) 624 return 1; 625 626 for (i = 1; i < wraps->mat->n_col; ++i) 627 if (isl_int_abs_gt(wraps->mat->row[row][i], wraps->max)) 628 return 0; 629 630 return 1; 631} 632 633/* For each non-redundant constraint in "bmap" (as determined by "tab"), 634 * wrap the constraint around "bound" such that it includes the whole 635 * set "set" and append the resulting constraint to "wraps". 636 * "wraps" is assumed to have been pre-allocated to the appropriate size. 637 * wraps->n_row is the number of actual wrapped constraints that have 638 * been added. 639 * If any of the wrapping problems results in a constraint that is 640 * identical to "bound", then this means that "set" is unbounded in such 641 * way that no wrapping is possible. If this happens then wraps->n_row 642 * is reset to zero. 643 * Similarly, if we want to bound the coefficients of the wrapping 644 * constraints and a newly added wrapping constraint does not 645 * satisfy the bound, then wraps->n_row is also reset to zero. 646 */ 647static int add_wraps(struct isl_wraps *wraps, __isl_keep isl_basic_map *bmap, 648 struct isl_tab *tab, isl_int *bound, __isl_keep isl_set *set) 649{ 650 int l; 651 int w; 652 unsigned total = isl_basic_map_total_dim(bmap); 653 654 w = wraps->mat->n_row; 655 656 for (l = 0; l < bmap->n_ineq; ++l) { 657 if (isl_seq_is_neg(bound, bmap->ineq[l], 1 + total)) 658 continue; 659 if (isl_seq_eq(bound, bmap->ineq[l], 1 + total)) 660 continue; 661 if (isl_tab_is_redundant(tab, bmap->n_eq + l)) 662 continue; 663 664 isl_seq_cpy(wraps->mat->row[w], bound, 1 + total); 665 if (!isl_set_wrap_facet(set, wraps->mat->row[w], bmap->ineq[l])) 666 return -1; 667 if (isl_seq_eq(wraps->mat->row[w], bound, 1 + total)) 668 goto unbounded; 669 if (!allow_wrap(wraps, w)) 670 goto unbounded; 671 ++w; 672 } 673 for (l = 0; l < bmap->n_eq; ++l) { 674 if (isl_seq_is_neg(bound, bmap->eq[l], 1 + total)) 675 continue; 676 if (isl_seq_eq(bound, bmap->eq[l], 1 + total)) 677 continue; 678 679 isl_seq_cpy(wraps->mat->row[w], bound, 1 + total); 680 isl_seq_neg(wraps->mat->row[w + 1], bmap->eq[l], 1 + total); 681 if (!isl_set_wrap_facet(set, wraps->mat->row[w], 682 wraps->mat->row[w + 1])) 683 return -1; 684 if (isl_seq_eq(wraps->mat->row[w], bound, 1 + total)) 685 goto unbounded; 686 if (!allow_wrap(wraps, w)) 687 goto unbounded; 688 ++w; 689 690 isl_seq_cpy(wraps->mat->row[w], bound, 1 + total); 691 if (!isl_set_wrap_facet(set, wraps->mat->row[w], bmap->eq[l])) 692 return -1; 693 if (isl_seq_eq(wraps->mat->row[w], bound, 1 + total)) 694 goto unbounded; 695 if (!allow_wrap(wraps, w)) 696 goto unbounded; 697 ++w; 698 } 699 700 wraps->mat->n_row = w; 701 return 0; 702unbounded: 703 wraps->mat->n_row = 0; 704 return 0; 705} 706 707/* Check if the constraints in "wraps" from "first" until the last 708 * are all valid for the basic set represented by "tab". 709 * If not, wraps->n_row is set to zero. 710 */ 711static int check_wraps(__isl_keep isl_mat *wraps, int first, 712 struct isl_tab *tab) 713{ 714 int i; 715 716 for (i = first; i < wraps->n_row; ++i) { 717 enum isl_ineq_type type; 718 type = isl_tab_ineq_type(tab, wraps->row[i]); 719 if (type == isl_ineq_error) 720 return -1; 721 if (type == isl_ineq_redundant) 722 continue; 723 wraps->n_row = 0; 724 return 0; 725 } 726 727 return 0; 728} 729 730/* Return a set that corresponds to the non-redudant constraints 731 * (as recorded in tab) of bmap. 732 * 733 * It's important to remove the redundant constraints as some 734 * of the other constraints may have been modified after the 735 * constraints were marked redundant. 736 * In particular, a constraint may have been relaxed. 737 * Redundant constraints are ignored when a constraint is relaxed 738 * and should therefore continue to be ignored ever after. 739 * Otherwise, the relaxation might be thwarted by some of 740 * these constraints. 741 */ 742static __isl_give isl_set *set_from_updated_bmap(__isl_keep isl_basic_map *bmap, 743 struct isl_tab *tab) 744{ 745 bmap = isl_basic_map_copy(bmap); 746 bmap = isl_basic_map_cow(bmap); 747 bmap = isl_basic_map_update_from_tab(bmap, tab); 748 return isl_set_from_basic_set(isl_basic_map_underlying_set(bmap)); 749} 750 751/* Given a basic set i with a constraint k that is adjacent to either the 752 * whole of basic set j or a facet of basic set j, check if we can wrap 753 * both the facet corresponding to k and the facet of j (or the whole of j) 754 * around their ridges to include the other set. 755 * If so, replace the pair of basic sets by their union. 756 * 757 * All constraints of i (except k) are assumed to be valid for j. 758 * 759 * However, the constraints of j may not be valid for i and so 760 * we have to check that the wrapping constraints for j are valid for i. 761 * 762 * In the case where j has a facet adjacent to i, tab[j] is assumed 763 * to have been restricted to this facet, so that the non-redundant 764 * constraints in tab[j] are the ridges of the facet. 765 * Note that for the purpose of wrapping, it does not matter whether 766 * we wrap the ridges of i around the whole of j or just around 767 * the facet since all the other constraints are assumed to be valid for j. 768 * In practice, we wrap to include the whole of j. 769 * ____ _____ 770 * / | / \ 771 * / || / | 772 * \ || => \ | 773 * \ || \ | 774 * \___|| \____| 775 * 776 */ 777static int can_wrap_in_facet(struct isl_map *map, int i, int j, int k, 778 struct isl_tab **tabs, int *eq_i, int *ineq_i, int *eq_j, int *ineq_j) 779{ 780 int changed = 0; 781 struct isl_wraps wraps; 782 isl_mat *mat; 783 struct isl_set *set_i = NULL; 784 struct isl_set *set_j = NULL; 785 struct isl_vec *bound = NULL; 786 unsigned total = isl_basic_map_total_dim(map->p[i]); 787 struct isl_tab_undo *snap; 788 int n; 789 790 set_i = set_from_updated_bmap(map->p[i], tabs[i]); 791 set_j = set_from_updated_bmap(map->p[j], tabs[j]); 792 mat = isl_mat_alloc(map->ctx, 2 * (map->p[i]->n_eq + map->p[j]->n_eq) + 793 map->p[i]->n_ineq + map->p[j]->n_ineq, 794 1 + total); 795 wraps_init(&wraps, mat, map, i, j, eq_i, ineq_i, eq_j, ineq_j); 796 bound = isl_vec_alloc(map->ctx, 1 + total); 797 if (!set_i || !set_j || !wraps.mat || !bound) 798 goto error; 799 800 isl_seq_cpy(bound->el, map->p[i]->ineq[k], 1 + total); 801 isl_int_add_ui(bound->el[0], bound->el[0], 1); 802 803 isl_seq_cpy(wraps.mat->row[0], bound->el, 1 + total); 804 wraps.mat->n_row = 1; 805 806 if (add_wraps(&wraps, map->p[j], tabs[j], bound->el, set_i) < 0) 807 goto error; 808 if (!wraps.mat->n_row) 809 goto unbounded; 810 811 snap = isl_tab_snap(tabs[i]); 812 813 if (isl_tab_select_facet(tabs[i], map->p[i]->n_eq + k) < 0) 814 goto error; 815 if (isl_tab_detect_redundant(tabs[i]) < 0) 816 goto error; 817 818 isl_seq_neg(bound->el, map->p[i]->ineq[k], 1 + total); 819 820 n = wraps.mat->n_row; 821 if (add_wraps(&wraps, map->p[i], tabs[i], bound->el, set_j) < 0) 822 goto error; 823 824 if (isl_tab_rollback(tabs[i], snap) < 0) 825 goto error; 826 if (check_wraps(wraps.mat, n, tabs[i]) < 0) 827 goto error; 828 if (!wraps.mat->n_row) 829 goto unbounded; 830 831 changed = fuse(map, i, j, tabs, eq_i, ineq_i, eq_j, ineq_j, wraps.mat); 832 833unbounded: 834 wraps_free(&wraps); 835 836 isl_set_free(set_i); 837 isl_set_free(set_j); 838 839 isl_vec_free(bound); 840 841 return changed; 842error: 843 wraps_free(&wraps); 844 isl_vec_free(bound); 845 isl_set_free(set_i); 846 isl_set_free(set_j); 847 return -1; 848} 849 850/* Set the is_redundant property of the "n" constraints in "cuts", 851 * except "k" to "v". 852 * This is a fairly tricky operation as it bypasses isl_tab.c. 853 * The reason we want to temporarily mark some constraints redundant 854 * is that we want to ignore them in add_wraps. 855 * 856 * Initially all cut constraints are non-redundant, but the 857 * selection of a facet right before the call to this function 858 * may have made some of them redundant. 859 * Likewise, the same constraints are marked non-redundant 860 * in the second call to this function, before they are officially 861 * made non-redundant again in the subsequent rollback. 862 */ 863static void set_is_redundant(struct isl_tab *tab, unsigned n_eq, 864 int *cuts, int n, int k, int v) 865{ 866 int l; 867 868 for (l = 0; l < n; ++l) { 869 if (l == k) 870 continue; 871 tab->con[n_eq + cuts[l]].is_redundant = v; 872 } 873} 874 875/* Given a pair of basic maps i and j such that j sticks out 876 * of i at n cut constraints, each time by at most one, 877 * try to compute wrapping constraints and replace the two 878 * basic maps by a single basic map. 879 * The other constraints of i are assumed to be valid for j. 880 * 881 * The facets of i corresponding to the cut constraints are 882 * wrapped around their ridges, except those ridges determined 883 * by any of the other cut constraints. 884 * The intersections of cut constraints need to be ignored 885 * as the result of wrapping one cut constraint around another 886 * would result in a constraint cutting the union. 887 * In each case, the facets are wrapped to include the union 888 * of the two basic maps. 889 * 890 * The pieces of j that lie at an offset of exactly one from 891 * one of the cut constraints of i are wrapped around their edges. 892 * Here, there is no need to ignore intersections because we 893 * are wrapping around the union of the two basic maps. 894 * 895 * If any wrapping fails, i.e., if we cannot wrap to touch 896 * the union, then we give up. 897 * Otherwise, the pair of basic maps is replaced by their union. 898 */ 899static int wrap_in_facets(struct isl_map *map, int i, int j, 900 int *cuts, int n, struct isl_tab **tabs, 901 int *eq_i, int *ineq_i, int *eq_j, int *ineq_j) 902{ 903 int changed = 0; 904 struct isl_wraps wraps; 905 isl_mat *mat; 906 isl_set *set = NULL; 907 isl_vec *bound = NULL; 908 unsigned total = isl_basic_map_total_dim(map->p[i]); 909 int max_wrap; 910 int k; 911 struct isl_tab_undo *snap_i, *snap_j; 912 913 if (isl_tab_extend_cons(tabs[j], 1) < 0) 914 goto error; 915 916 max_wrap = 2 * (map->p[i]->n_eq + map->p[j]->n_eq) + 917 map->p[i]->n_ineq + map->p[j]->n_ineq; 918 max_wrap *= n; 919 920 set = isl_set_union(set_from_updated_bmap(map->p[i], tabs[i]), 921 set_from_updated_bmap(map->p[j], tabs[j])); 922 mat = isl_mat_alloc(map->ctx, max_wrap, 1 + total); 923 wraps_init(&wraps, mat, map, i, j, eq_i, ineq_i, eq_j, ineq_j); 924 bound = isl_vec_alloc(map->ctx, 1 + total); 925 if (!set || !wraps.mat || !bound) 926 goto error; 927 928 snap_i = isl_tab_snap(tabs[i]); 929 snap_j = isl_tab_snap(tabs[j]); 930 931 wraps.mat->n_row = 0; 932 933 for (k = 0; k < n; ++k) { 934 if (isl_tab_select_facet(tabs[i], map->p[i]->n_eq + cuts[k]) < 0) 935 goto error; 936 if (isl_tab_detect_redundant(tabs[i]) < 0) 937 goto error; 938 set_is_redundant(tabs[i], map->p[i]->n_eq, cuts, n, k, 1); 939 940 isl_seq_neg(bound->el, map->p[i]->ineq[cuts[k]], 1 + total); 941 if (!tabs[i]->empty && 942 add_wraps(&wraps, map->p[i], tabs[i], bound->el, set) < 0) 943 goto error; 944 945 set_is_redundant(tabs[i], map->p[i]->n_eq, cuts, n, k, 0); 946 if (isl_tab_rollback(tabs[i], snap_i) < 0) 947 goto error; 948 949 if (tabs[i]->empty) 950 break; 951 if (!wraps.mat->n_row) 952 break; 953 954 isl_seq_cpy(bound->el, map->p[i]->ineq[cuts[k]], 1 + total); 955 isl_int_add_ui(bound->el[0], bound->el[0], 1); 956 if (isl_tab_add_eq(tabs[j], bound->el) < 0) 957 goto error; 958 if (isl_tab_detect_redundant(tabs[j]) < 0) 959 goto error; 960 961 if (!tabs[j]->empty && 962 add_wraps(&wraps, map->p[j], tabs[j], bound->el, set) < 0) 963 goto error; 964 965 if (isl_tab_rollback(tabs[j], snap_j) < 0) 966 goto error; 967 968 if (!wraps.mat->n_row) 969 break; 970 } 971 972 if (k == n) 973 changed = fuse(map, i, j, tabs, 974 eq_i, ineq_i, eq_j, ineq_j, wraps.mat); 975 976 isl_vec_free(bound); 977 wraps_free(&wraps); 978 isl_set_free(set); 979 980 return changed; 981error: 982 isl_vec_free(bound); 983 wraps_free(&wraps); 984 isl_set_free(set); 985 return -1; 986} 987 988/* Given two basic sets i and j such that i has no cut equalities, 989 * check if relaxing all the cut inequalities of i by one turns 990 * them into valid constraint for j and check if we can wrap in 991 * the bits that are sticking out. 992 * If so, replace the pair by their union. 993 * 994 * We first check if all relaxed cut inequalities of i are valid for j 995 * and then try to wrap in the intersections of the relaxed cut inequalities 996 * with j. 997 * 998 * During this wrapping, we consider the points of j that lie at a distance 999 * of exactly 1 from i. In particular, we ignore the points that lie in 1000 * between this lower-dimensional space and the basic map i. 1001 * We can therefore only apply this to integer maps. 1002 * ____ _____ 1003 * / ___|_ / \ 1004 * / | | / | 1005 * \ | | => \ | 1006 * \|____| \ | 1007 * \___| \____/ 1008 * 1009 * _____ ______ 1010 * | ____|_ | \ 1011 * | | | | | 1012 * | | | => | | 1013 * |_| | | | 1014 * |_____| \______| 1015 * 1016 * _______ 1017 * | | 1018 * | |\ | 1019 * | | \ | 1020 * | | \ | 1021 * | | \| 1022 * | | \ 1023 * | |_____\ 1024 * | | 1025 * |_______| 1026 * 1027 * Wrapping can fail if the result of wrapping one of the facets 1028 * around its edges does not produce any new facet constraint. 1029 * In particular, this happens when we try to wrap in unbounded sets. 1030 * 1031 * _______________________________________________________________________ 1032 * | 1033 * | ___ 1034 * | | | 1035 * |_| |_________________________________________________________________ 1036 * |___| 1037 * 1038 * The following is not an acceptable result of coalescing the above two 1039 * sets as it includes extra integer points. 1040 * _______________________________________________________________________ 1041 * | 1042 * | 1043 * | 1044 * | 1045 * \______________________________________________________________________ 1046 */ 1047static int can_wrap_in_set(struct isl_map *map, int i, int j, 1048 struct isl_tab **tabs, int *eq_i, int *ineq_i, int *eq_j, int *ineq_j) 1049{ 1050 int changed = 0; 1051 int k, m; 1052 int n; 1053 int *cuts = NULL; 1054 1055 if (ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_RATIONAL) || 1056 ISL_F_ISSET(map->p[j], ISL_BASIC_MAP_RATIONAL)) 1057 return 0; 1058 1059 n = count(ineq_i, map->p[i]->n_ineq, STATUS_CUT); 1060 if (n == 0) 1061 return 0; 1062 1063 cuts = isl_alloc_array(map->ctx, int, n); 1064 if (!cuts) 1065 return -1; 1066 1067 for (k = 0, m = 0; m < n; ++k) { 1068 enum isl_ineq_type type; 1069 1070 if (ineq_i[k] != STATUS_CUT) 1071 continue; 1072 1073 isl_int_add_ui(map->p[i]->ineq[k][0], map->p[i]->ineq[k][0], 1); 1074 type = isl_tab_ineq_type(tabs[j], map->p[i]->ineq[k]); 1075 isl_int_sub_ui(map->p[i]->ineq[k][0], map->p[i]->ineq[k][0], 1); 1076 if (type == isl_ineq_error) 1077 goto error; 1078 if (type != isl_ineq_redundant) 1079 break; 1080 cuts[m] = k; 1081 ++m; 1082 } 1083 1084 if (m == n) 1085 changed = wrap_in_facets(map, i, j, cuts, n, tabs, 1086 eq_i, ineq_i, eq_j, ineq_j); 1087 1088 free(cuts); 1089 1090 return changed; 1091error: 1092 free(cuts); 1093 return -1; 1094} 1095 1096/* Check if either i or j has a single cut constraint that can 1097 * be used to wrap in (a facet of) the other basic set. 1098 * if so, replace the pair by their union. 1099 */ 1100static int check_wrap(struct isl_map *map, int i, int j, 1101 struct isl_tab **tabs, int *eq_i, int *ineq_i, int *eq_j, int *ineq_j) 1102{ 1103 int changed = 0; 1104 1105 if (!any(eq_i, 2 * map->p[i]->n_eq, STATUS_CUT)) 1106 changed = can_wrap_in_set(map, i, j, tabs, 1107 eq_i, ineq_i, eq_j, ineq_j); 1108 if (changed) 1109 return changed; 1110 1111 if (!any(eq_j, 2 * map->p[j]->n_eq, STATUS_CUT)) 1112 changed = can_wrap_in_set(map, j, i, tabs, 1113 eq_j, ineq_j, eq_i, ineq_i); 1114 return changed; 1115} 1116 1117/* At least one of the basic maps has an equality that is adjacent 1118 * to inequality. Make sure that only one of the basic maps has 1119 * such an equality and that the other basic map has exactly one 1120 * inequality adjacent to an equality. 1121 * We call the basic map that has the inequality "i" and the basic 1122 * map that has the equality "j". 1123 * If "i" has any "cut" (in)equality, then relaxing the inequality 1124 * by one would not result in a basic map that contains the other 1125 * basic map. 1126 */ 1127static int check_adj_eq(struct isl_map *map, int i, int j, 1128 struct isl_tab **tabs, int *eq_i, int *ineq_i, int *eq_j, int *ineq_j) 1129{ 1130 int changed = 0; 1131 int k; 1132 1133 if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_INEQ) && 1134 any(eq_j, 2 * map->p[j]->n_eq, STATUS_ADJ_INEQ)) 1135 /* ADJ EQ TOO MANY */ 1136 return 0; 1137 1138 if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_INEQ)) 1139 return check_adj_eq(map, j, i, tabs, 1140 eq_j, ineq_j, eq_i, ineq_i); 1141 1142 /* j has an equality adjacent to an inequality in i */ 1143 1144 if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_CUT)) 1145 return 0; 1146 if (any(ineq_i, map->p[i]->n_ineq, STATUS_CUT)) 1147 /* ADJ EQ CUT */ 1148 return 0; 1149 if (count(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_EQ) != 1 || 1150 any(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_EQ) || 1151 any(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_INEQ) || 1152 any(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_INEQ)) 1153 /* ADJ EQ TOO MANY */ 1154 return 0; 1155 1156 for (k = 0; k < map->p[i]->n_ineq; ++k) 1157 if (ineq_i[k] == STATUS_ADJ_EQ) 1158 break; 1159 1160 changed = is_adj_eq_extension(map, i, j, k, tabs, 1161 eq_i, ineq_i, eq_j, ineq_j); 1162 if (changed) 1163 return changed; 1164 1165 if (count(eq_j, 2 * map->p[j]->n_eq, STATUS_ADJ_INEQ) != 1) 1166 return 0; 1167 1168 changed = can_wrap_in_facet(map, i, j, k, tabs, eq_i, ineq_i, eq_j, ineq_j); 1169 1170 return changed; 1171} 1172 1173/* The two basic maps lie on adjacent hyperplanes. In particular, 1174 * basic map "i" has an equality that lies parallel to basic map "j". 1175 * Check if we can wrap the facets around the parallel hyperplanes 1176 * to include the other set. 1177 * 1178 * We perform basically the same operations as can_wrap_in_facet, 1179 * except that we don't need to select a facet of one of the sets. 1180 * _ 1181 * \\ \\ 1182 * \\ => \\ 1183 * \ \| 1184 * 1185 * We only allow one equality of "i" to be adjacent to an equality of "j" 1186 * to avoid coalescing 1187 * 1188 * [m, n] -> { [x, y] -> [x, 1 + y] : x >= 1 and y >= 1 and 1189 * x <= 10 and y <= 10; 1190 * [x, y] -> [1 + x, y] : x >= 1 and x <= 20 and 1191 * y >= 5 and y <= 15 } 1192 * 1193 * to 1194 * 1195 * [m, n] -> { [x, y] -> [x2, y2] : x >= 1 and 10y2 <= 20 - x + 10y and 1196 * 4y2 >= 5 + 3y and 5y2 <= 15 + 4y and 1197 * y2 <= 1 + x + y - x2 and y2 >= y and 1198 * y2 >= 1 + x + y - x2 } 1199 */ 1200static int check_eq_adj_eq(struct isl_map *map, int i, int j, 1201 struct isl_tab **tabs, int *eq_i, int *ineq_i, int *eq_j, int *ineq_j) 1202{ 1203 int k; 1204 int changed = 0; 1205 struct isl_wraps wraps; 1206 isl_mat *mat; 1207 struct isl_set *set_i = NULL; 1208 struct isl_set *set_j = NULL; 1209 struct isl_vec *bound = NULL; 1210 unsigned total = isl_basic_map_total_dim(map->p[i]); 1211 1212 if (count(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_EQ) != 1) 1213 return 0; 1214 1215 for (k = 0; k < 2 * map->p[i]->n_eq ; ++k) 1216 if (eq_i[k] == STATUS_ADJ_EQ) 1217 break; 1218 1219 set_i = set_from_updated_bmap(map->p[i], tabs[i]); 1220 set_j = set_from_updated_bmap(map->p[j], tabs[j]); 1221 mat = isl_mat_alloc(map->ctx, 2 * (map->p[i]->n_eq + map->p[j]->n_eq) + 1222 map->p[i]->n_ineq + map->p[j]->n_ineq, 1223 1 + total); 1224 wraps_init(&wraps, mat, map, i, j, eq_i, ineq_i, eq_j, ineq_j); 1225 bound = isl_vec_alloc(map->ctx, 1 + total); 1226 if (!set_i || !set_j || !wraps.mat || !bound) 1227 goto error; 1228 1229 if (k % 2 == 0) 1230 isl_seq_neg(bound->el, map->p[i]->eq[k / 2], 1 + total); 1231 else 1232 isl_seq_cpy(bound->el, map->p[i]->eq[k / 2], 1 + total); 1233 isl_int_add_ui(bound->el[0], bound->el[0], 1); 1234 1235 isl_seq_cpy(wraps.mat->row[0], bound->el, 1 + total); 1236 wraps.mat->n_row = 1; 1237 1238 if (add_wraps(&wraps, map->p[j], tabs[j], bound->el, set_i) < 0) 1239 goto error; 1240 if (!wraps.mat->n_row) 1241 goto unbounded; 1242 1243 isl_int_sub_ui(bound->el[0], bound->el[0], 1); 1244 isl_seq_neg(bound->el, bound->el, 1 + total); 1245 1246 isl_seq_cpy(wraps.mat->row[wraps.mat->n_row], bound->el, 1 + total); 1247 wraps.mat->n_row++; 1248 1249 if (add_wraps(&wraps, map->p[i], tabs[i], bound->el, set_j) < 0) 1250 goto error; 1251 if (!wraps.mat->n_row) 1252 goto unbounded; 1253 1254 changed = fuse(map, i, j, tabs, eq_i, ineq_i, eq_j, ineq_j, wraps.mat); 1255 1256 if (0) { 1257error: changed = -1; 1258 } 1259unbounded: 1260 1261 wraps_free(&wraps); 1262 isl_set_free(set_i); 1263 isl_set_free(set_j); 1264 isl_vec_free(bound); 1265 1266 return changed; 1267} 1268 1269/* Check if the union of the given pair of basic maps 1270 * can be represented by a single basic map. 1271 * If so, replace the pair by the single basic map and return 1. 1272 * Otherwise, return 0; 1273 * The two basic maps are assumed to live in the same local space. 1274 * 1275 * We first check the effect of each constraint of one basic map 1276 * on the other basic map. 1277 * The constraint may be 1278 * redundant the constraint is redundant in its own 1279 * basic map and should be ignore and removed 1280 * in the end 1281 * valid all (integer) points of the other basic map 1282 * satisfy the constraint 1283 * separate no (integer) point of the other basic map 1284 * satisfies the constraint 1285 * cut some but not all points of the other basic map 1286 * satisfy the constraint 1287 * adj_eq the given constraint is adjacent (on the outside) 1288 * to an equality of the other basic map 1289 * adj_ineq the given constraint is adjacent (on the outside) 1290 * to an inequality of the other basic map 1291 * 1292 * We consider seven cases in which we can replace the pair by a single 1293 * basic map. We ignore all "redundant" constraints. 1294 * 1295 * 1. all constraints of one basic map are valid 1296 * => the other basic map is a subset and can be removed 1297 * 1298 * 2. all constraints of both basic maps are either "valid" or "cut" 1299 * and the facets corresponding to the "cut" constraints 1300 * of one of the basic maps lies entirely inside the other basic map 1301 * => the pair can be replaced by a basic map consisting 1302 * of the valid constraints in both basic maps 1303 * 1304 * 3. there is a single pair of adjacent inequalities 1305 * (all other constraints are "valid") 1306 * => the pair can be replaced by a basic map consisting 1307 * of the valid constraints in both basic maps 1308 * 1309 * 4. one basic map has a single adjacent inequality, while the other 1310 * constraints are "valid". The other basic map has some 1311 * "cut" constraints, but replacing the adjacent inequality by 1312 * its opposite and adding the valid constraints of the other 1313 * basic map results in a subset of the other basic map 1314 * => the pair can be replaced by a basic map consisting 1315 * of the valid constraints in both basic maps 1316 * 1317 * 5. there is a single adjacent pair of an inequality and an equality, 1318 * the other constraints of the basic map containing the inequality are 1319 * "valid". Moreover, if the inequality the basic map is relaxed 1320 * and then turned into an equality, then resulting facet lies 1321 * entirely inside the other basic map 1322 * => the pair can be replaced by the basic map containing 1323 * the inequality, with the inequality relaxed. 1324 * 1325 * 6. there is a single adjacent pair of an inequality and an equality, 1326 * the other constraints of the basic map containing the inequality are 1327 * "valid". Moreover, the facets corresponding to both 1328 * the inequality and the equality can be wrapped around their 1329 * ridges to include the other basic map 1330 * => the pair can be replaced by a basic map consisting 1331 * of the valid constraints in both basic maps together 1332 * with all wrapping constraints 1333 * 1334 * 7. one of the basic maps extends beyond the other by at most one. 1335 * Moreover, the facets corresponding to the cut constraints and 1336 * the pieces of the other basic map at offset one from these cut 1337 * constraints can be wrapped around their ridges to include 1338 * the union of the two basic maps 1339 * => the pair can be replaced by a basic map consisting 1340 * of the valid constraints in both basic maps together 1341 * with all wrapping constraints 1342 * 1343 * 8. the two basic maps live in adjacent hyperplanes. In principle 1344 * such sets can always be combined through wrapping, but we impose 1345 * that there is only one such pair, to avoid overeager coalescing. 1346 * 1347 * Throughout the computation, we maintain a collection of tableaus 1348 * corresponding to the basic maps. When the basic maps are dropped 1349 * or combined, the tableaus are modified accordingly. 1350 */ 1351static int coalesce_local_pair(__isl_keep isl_map *map, int i, int j, 1352 struct isl_tab **tabs) 1353{ 1354 int changed = 0; 1355 int *eq_i = NULL; 1356 int *eq_j = NULL; 1357 int *ineq_i = NULL; 1358 int *ineq_j = NULL; 1359 1360 eq_i = eq_status_in(map->p[i], tabs[j]); 1361 if (map->p[i]->n_eq && !eq_i) 1362 goto error; 1363 if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ERROR)) 1364 goto error; 1365 if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_SEPARATE)) 1366 goto done; 1367 1368 eq_j = eq_status_in(map->p[j], tabs[i]); 1369 if (map->p[j]->n_eq && !eq_j) 1370 goto error; 1371 if (any(eq_j, 2 * map->p[j]->n_eq, STATUS_ERROR)) 1372 goto error; 1373 if (any(eq_j, 2 * map->p[j]->n_eq, STATUS_SEPARATE)) 1374 goto done; 1375 1376 ineq_i = ineq_status_in(map->p[i], tabs[i], tabs[j]); 1377 if (map->p[i]->n_ineq && !ineq_i) 1378 goto error; 1379 if (any(ineq_i, map->p[i]->n_ineq, STATUS_ERROR)) 1380 goto error; 1381 if (any(ineq_i, map->p[i]->n_ineq, STATUS_SEPARATE)) 1382 goto done; 1383 1384 ineq_j = ineq_status_in(map->p[j], tabs[j], tabs[i]); 1385 if (map->p[j]->n_ineq && !ineq_j) 1386 goto error; 1387 if (any(ineq_j, map->p[j]->n_ineq, STATUS_ERROR)) 1388 goto error; 1389 if (any(ineq_j, map->p[j]->n_ineq, STATUS_SEPARATE)) 1390 goto done; 1391 1392 if (all(eq_i, 2 * map->p[i]->n_eq, STATUS_VALID) && 1393 all(ineq_i, map->p[i]->n_ineq, STATUS_VALID)) { 1394 drop(map, j, tabs); 1395 changed = 1; 1396 } else if (all(eq_j, 2 * map->p[j]->n_eq, STATUS_VALID) && 1397 all(ineq_j, map->p[j]->n_ineq, STATUS_VALID)) { 1398 drop(map, i, tabs); 1399 changed = 1; 1400 } else if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_EQ)) { 1401 changed = check_eq_adj_eq(map, i, j, tabs, 1402 eq_i, ineq_i, eq_j, ineq_j); 1403 } else if (any(eq_j, 2 * map->p[j]->n_eq, STATUS_ADJ_EQ)) { 1404 changed = check_eq_adj_eq(map, j, i, tabs, 1405 eq_j, ineq_j, eq_i, ineq_i); 1406 } else if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_INEQ) || 1407 any(eq_j, 2 * map->p[j]->n_eq, STATUS_ADJ_INEQ)) { 1408 changed = check_adj_eq(map, i, j, tabs, 1409 eq_i, ineq_i, eq_j, ineq_j); 1410 } else if (any(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_EQ) || 1411 any(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_EQ)) { 1412 /* Can't happen */ 1413 /* BAD ADJ INEQ */ 1414 } else if (any(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_INEQ) || 1415 any(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_INEQ)) { 1416 changed = check_adj_ineq(map, i, j, tabs, 1417 eq_i, ineq_i, eq_j, ineq_j); 1418 } else { 1419 if (!any(eq_i, 2 * map->p[i]->n_eq, STATUS_CUT) && 1420 !any(eq_j, 2 * map->p[j]->n_eq, STATUS_CUT)) 1421 changed = check_facets(map, i, j, tabs, ineq_i, ineq_j); 1422 if (!changed) 1423 changed = check_wrap(map, i, j, tabs, 1424 eq_i, ineq_i, eq_j, ineq_j); 1425 } 1426 1427done: 1428 free(eq_i); 1429 free(eq_j); 1430 free(ineq_i); 1431 free(ineq_j); 1432 return changed; 1433error: 1434 free(eq_i); 1435 free(eq_j); 1436 free(ineq_i); 1437 free(ineq_j); 1438 return -1; 1439} 1440 1441/* Do the two basic maps live in the same local space, i.e., 1442 * do they have the same (known) divs? 1443 * If either basic map has any unknown divs, then we can only assume 1444 * that they do not live in the same local space. 1445 */ 1446static int same_divs(__isl_keep isl_basic_map *bmap1, 1447 __isl_keep isl_basic_map *bmap2) 1448{ 1449 int i; 1450 int known; 1451 int total; 1452 1453 if (!bmap1 || !bmap2) 1454 return -1; 1455 if (bmap1->n_div != bmap2->n_div) 1456 return 0; 1457 1458 if (bmap1->n_div == 0) 1459 return 1; 1460 1461 known = isl_basic_map_divs_known(bmap1); 1462 if (known < 0 || !known) 1463 return known; 1464 known = isl_basic_map_divs_known(bmap2); 1465 if (known < 0 || !known) 1466 return known; 1467 1468 total = isl_basic_map_total_dim(bmap1); 1469 for (i = 0; i < bmap1->n_div; ++i) 1470 if (!isl_seq_eq(bmap1->div[i], bmap2->div[i], 2 + total)) 1471 return 0; 1472 1473 return 1; 1474} 1475 1476/* Given two basic maps "i" and "j", where the divs of "i" form a subset 1477 * of those of "j", check if basic map "j" is a subset of basic map "i" 1478 * and, if so, drop basic map "j". 1479 * 1480 * We first expand the divs of basic map "i" to match those of basic map "j", 1481 * using the divs and expansion computed by the caller. 1482 * Then we check if all constraints of the expanded "i" are valid for "j". 1483 */ 1484static int coalesce_subset(__isl_keep isl_map *map, int i, int j, 1485 struct isl_tab **tabs, __isl_keep isl_mat *div, int *exp) 1486{ 1487 isl_basic_map *bmap; 1488 int changed = 0; 1489 int *eq_i = NULL; 1490 int *ineq_i = NULL; 1491 1492 bmap = isl_basic_map_copy(map->p[i]); 1493 bmap = isl_basic_set_expand_divs(bmap, isl_mat_copy(div), exp); 1494 1495 if (!bmap) 1496 goto error; 1497 1498 eq_i = eq_status_in(bmap, tabs[j]); 1499 if (bmap->n_eq && !eq_i) 1500 goto error; 1501 if (any(eq_i, 2 * bmap->n_eq, STATUS_ERROR)) 1502 goto error; 1503 if (any(eq_i, 2 * bmap->n_eq, STATUS_SEPARATE)) 1504 goto done; 1505 1506 ineq_i = ineq_status_in(bmap, NULL, tabs[j]); 1507 if (bmap->n_ineq && !ineq_i) 1508 goto error; 1509 if (any(ineq_i, bmap->n_ineq, STATUS_ERROR)) 1510 goto error; 1511 if (any(ineq_i, bmap->n_ineq, STATUS_SEPARATE)) 1512 goto done; 1513 1514 if (all(eq_i, 2 * map->p[i]->n_eq, STATUS_VALID) && 1515 all(ineq_i, map->p[i]->n_ineq, STATUS_VALID)) { 1516 drop(map, j, tabs); 1517 changed = 1; 1518 } 1519 1520done: 1521 isl_basic_map_free(bmap); 1522 free(eq_i); 1523 free(ineq_i); 1524 return 0; 1525error: 1526 isl_basic_map_free(bmap); 1527 free(eq_i); 1528 free(ineq_i); 1529 return -1; 1530} 1531 1532/* Check if the basic map "j" is a subset of basic map "i", 1533 * assuming that "i" has fewer divs that "j". 1534 * If not, then we change the order. 1535 * 1536 * If the two basic maps have the same number of divs, then 1537 * they must necessarily be different. Otherwise, we would have 1538 * called coalesce_local_pair. We therefore don't try anything 1539 * in this case. 1540 * 1541 * We first check if the divs of "i" are all known and form a subset 1542 * of those of "j". If so, we pass control over to coalesce_subset. 1543 */ 1544static int check_coalesce_subset(__isl_keep isl_map *map, int i, int j, 1545 struct isl_tab **tabs) 1546{ 1547 int known; 1548 isl_mat *div_i, *div_j, *div; 1549 int *exp1 = NULL; 1550 int *exp2 = NULL; 1551 isl_ctx *ctx; 1552 int subset; 1553 1554 if (map->p[i]->n_div == map->p[j]->n_div) 1555 return 0; 1556 if (map->p[j]->n_div < map->p[i]->n_div) 1557 return check_coalesce_subset(map, j, i, tabs); 1558 1559 known = isl_basic_map_divs_known(map->p[i]); 1560 if (known < 0 || !known) 1561 return known; 1562 1563 ctx = isl_map_get_ctx(map); 1564 1565 div_i = isl_basic_map_get_divs(map->p[i]); 1566 div_j = isl_basic_map_get_divs(map->p[j]); 1567 1568 if (!div_i || !div_j) 1569 goto error; 1570 1571 exp1 = isl_alloc_array(ctx, int, div_i->n_row); 1572 exp2 = isl_alloc_array(ctx, int, div_j->n_row); 1573 if ((div_i->n_row && !exp1) || (div_j->n_row && !exp2)) 1574 goto error; 1575 1576 div = isl_merge_divs(div_i, div_j, exp1, exp2); 1577 if (!div) 1578 goto error; 1579 1580 if (div->n_row == div_j->n_row) 1581 subset = coalesce_subset(map, i, j, tabs, div, exp1); 1582 else 1583 subset = 0; 1584 1585 isl_mat_free(div); 1586 1587 isl_mat_free(div_i); 1588 isl_mat_free(div_j); 1589 1590 free(exp2); 1591 free(exp1); 1592 1593 return subset; 1594error: 1595 isl_mat_free(div_i); 1596 isl_mat_free(div_j); 1597 free(exp1); 1598 free(exp2); 1599 return -1; 1600} 1601 1602/* Check if the union of the given pair of basic maps 1603 * can be represented by a single basic map. 1604 * If so, replace the pair by the single basic map and return 1. 1605 * Otherwise, return 0; 1606 * 1607 * We first check if the two basic maps live in the same local space. 1608 * If so, we do the complete check. Otherwise, we check if one is 1609 * an obvious subset of the other. 1610 */ 1611static int coalesce_pair(__isl_keep isl_map *map, int i, int j, 1612 struct isl_tab **tabs) 1613{ 1614 int same; 1615 1616 same = same_divs(map->p[i], map->p[j]); 1617 if (same < 0) 1618 return -1; 1619 if (same) 1620 return coalesce_local_pair(map, i, j, tabs); 1621 1622 return check_coalesce_subset(map, i, j, tabs); 1623} 1624 1625static struct isl_map *coalesce(struct isl_map *map, struct isl_tab **tabs) 1626{ 1627 int i, j; 1628 1629 for (i = map->n - 2; i >= 0; --i) 1630restart: 1631 for (j = i + 1; j < map->n; ++j) { 1632 int changed; 1633 changed = coalesce_pair(map, i, j, tabs); 1634 if (changed < 0) 1635 goto error; 1636 if (changed) 1637 goto restart; 1638 } 1639 return map; 1640error: 1641 isl_map_free(map); 1642 return NULL; 1643} 1644 1645/* For each pair of basic maps in the map, check if the union of the two 1646 * can be represented by a single basic map. 1647 * If so, replace the pair by the single basic map and start over. 1648 * 1649 * Since we are constructing the tableaus of the basic maps anyway, 1650 * we exploit them to detect implicit equalities and redundant constraints. 1651 * This also helps the coalescing as it can ignore the redundant constraints. 1652 * In order to avoid confusion, we make all implicit equalities explicit 1653 * in the basic maps. We don't call isl_basic_map_gauss, though, 1654 * as that may affect the number of constraints. 1655 * This means that we have to call isl_basic_map_gauss at the end 1656 * of the computation to ensure that the basic maps are not left 1657 * in an unexpected state. 1658 */ 1659struct isl_map *isl_map_coalesce(struct isl_map *map) 1660{ 1661 int i; 1662 unsigned n; 1663 struct isl_tab **tabs = NULL; 1664 1665 map = isl_map_remove_empty_parts(map); 1666 if (!map) 1667 return NULL; 1668 1669 if (map->n <= 1) 1670 return map; 1671 1672 map = isl_map_sort_divs(map); 1673 map = isl_map_cow(map); 1674 1675 tabs = isl_calloc_array(map->ctx, struct isl_tab *, map->n); 1676 if (!tabs) 1677 goto error; 1678 1679 n = map->n; 1680 for (i = 0; i < map->n; ++i) { 1681 tabs[i] = isl_tab_from_basic_map(map->p[i], 0); 1682 if (!tabs[i]) 1683 goto error; 1684 if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_NO_IMPLICIT)) 1685 if (isl_tab_detect_implicit_equalities(tabs[i]) < 0) 1686 goto error; 1687 map->p[i] = isl_tab_make_equalities_explicit(tabs[i], 1688 map->p[i]); 1689 if (!map->p[i]) 1690 goto error; 1691 if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_NO_REDUNDANT)) 1692 if (isl_tab_detect_redundant(tabs[i]) < 0) 1693 goto error; 1694 } 1695 for (i = map->n - 1; i >= 0; --i) 1696 if (tabs[i]->empty) 1697 drop(map, i, tabs); 1698 1699 map = coalesce(map, tabs); 1700 1701 if (map) 1702 for (i = 0; i < map->n; ++i) { 1703 map->p[i] = isl_basic_map_update_from_tab(map->p[i], 1704 tabs[i]); 1705 map->p[i] = isl_basic_map_gauss(map->p[i], NULL); 1706 map->p[i] = isl_basic_map_finalize(map->p[i]); 1707 if (!map->p[i]) 1708 goto error; 1709 ISL_F_SET(map->p[i], ISL_BASIC_MAP_NO_IMPLICIT); 1710 ISL_F_SET(map->p[i], ISL_BASIC_MAP_NO_REDUNDANT); 1711 } 1712 1713 for (i = 0; i < n; ++i) 1714 isl_tab_free(tabs[i]); 1715 1716 free(tabs); 1717 1718 return map; 1719error: 1720 if (tabs) 1721 for (i = 0; i < n; ++i) 1722 isl_tab_free(tabs[i]); 1723 free(tabs); 1724 isl_map_free(map); 1725 return NULL; 1726} 1727 1728/* For each pair of basic sets in the set, check if the union of the two 1729 * can be represented by a single basic set. 1730 * If so, replace the pair by the single basic set and start over. 1731 */ 1732struct isl_set *isl_set_coalesce(struct isl_set *set) 1733{ 1734 return (struct isl_set *)isl_map_coalesce((struct isl_map *)set); 1735} 1736