| File: | tools/polly/lib/External/isl/isl_coalesce.c |
| Warning: | line 2284, column 2 Value stored to 'total' is never read |
| 1 | /* |
| 2 | * Copyright 2008-2009 Katholieke Universiteit Leuven |
| 3 | * Copyright 2010 INRIA Saclay |
| 4 | * Copyright 2012-2013 Ecole Normale Superieure |
| 5 | * Copyright 2014 INRIA Rocquencourt |
| 6 | * Copyright 2016 INRIA Paris |
| 7 | * |
| 8 | * Use of this software is governed by the MIT license |
| 9 | * |
| 10 | * Written by Sven Verdoolaege, K.U.Leuven, Departement |
| 11 | * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium |
| 12 | * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite, |
| 13 | * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France |
| 14 | * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France |
| 15 | * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt, |
| 16 | * B.P. 105 - 78153 Le Chesnay, France |
| 17 | * and Centre de Recherche Inria de Paris, 2 rue Simone Iff - Voie DQ12, |
| 18 | * CS 42112, 75589 Paris Cedex 12, France |
| 19 | */ |
| 20 | |
| 21 | #include <isl_ctx_private.h> |
| 22 | #include "isl_map_private.h" |
| 23 | #include <isl_seq.h> |
| 24 | #include <isl/options.h> |
| 25 | #include "isl_tab.h" |
| 26 | #include <isl_mat_private.h> |
| 27 | #include <isl_local_space_private.h> |
| 28 | #include <isl_val_private.h> |
| 29 | #include <isl_vec_private.h> |
| 30 | #include <isl_aff_private.h> |
| 31 | #include <isl_equalities.h> |
| 32 | #include <isl_constraint_private.h> |
| 33 | |
| 34 | #include <set_to_map.c> |
| 35 | #include <set_from_map.c> |
| 36 | |
| 37 | #define STATUS_ERROR-1 -1 |
| 38 | #define STATUS_REDUNDANT1 1 |
| 39 | #define STATUS_VALID2 2 |
| 40 | #define STATUS_SEPARATE3 3 |
| 41 | #define STATUS_CUT4 4 |
| 42 | #define STATUS_ADJ_EQ5 5 |
| 43 | #define STATUS_ADJ_INEQ6 6 |
| 44 | |
| 45 | static int status_in(isl_int *ineq, struct isl_tab *tab) |
| 46 | { |
| 47 | enum isl_ineq_type type = isl_tab_ineq_type(tab, ineq); |
| 48 | switch (type) { |
| 49 | default: |
| 50 | case isl_ineq_error: return STATUS_ERROR-1; |
| 51 | case isl_ineq_redundant: return STATUS_VALID2; |
| 52 | case isl_ineq_separate: return STATUS_SEPARATE3; |
| 53 | case isl_ineq_cut: return STATUS_CUT4; |
| 54 | case isl_ineq_adj_eq: return STATUS_ADJ_EQ5; |
| 55 | case isl_ineq_adj_ineq: return STATUS_ADJ_INEQ6; |
| 56 | } |
| 57 | } |
| 58 | |
| 59 | /* Compute the position of the equalities of basic map "bmap_i" |
| 60 | * with respect to the basic map represented by "tab_j". |
| 61 | * The resulting array has twice as many entries as the number |
| 62 | * of equalities corresponding to the two inequalties to which |
| 63 | * each equality corresponds. |
| 64 | */ |
| 65 | static int *eq_status_in(__isl_keep isl_basic_map *bmap_i, |
| 66 | struct isl_tab *tab_j) |
| 67 | { |
| 68 | int k, l; |
| 69 | int *eq = isl_calloc_array(bmap_i->ctx, int, 2 * bmap_i->n_eq)((int *)isl_calloc_or_die(bmap_i->ctx, 2 * bmap_i->n_eq , sizeof(int))); |
| 70 | unsigned dim; |
| 71 | |
| 72 | if (!eq) |
| 73 | return NULL((void*)0); |
| 74 | |
| 75 | dim = isl_basic_map_total_dim(bmap_i); |
| 76 | for (k = 0; k < bmap_i->n_eq; ++k) { |
| 77 | for (l = 0; l < 2; ++l) { |
| 78 | isl_seq_neg(bmap_i->eq[k], bmap_i->eq[k], 1+dim); |
| 79 | eq[2 * k + l] = status_in(bmap_i->eq[k], tab_j); |
| 80 | if (eq[2 * k + l] == STATUS_ERROR-1) |
| 81 | goto error; |
| 82 | } |
| 83 | if (eq[2 * k] == STATUS_SEPARATE3 || |
| 84 | eq[2 * k + 1] == STATUS_SEPARATE3) |
| 85 | break; |
| 86 | } |
| 87 | |
| 88 | return eq; |
| 89 | error: |
| 90 | free(eq); |
| 91 | return NULL((void*)0); |
| 92 | } |
| 93 | |
| 94 | /* Compute the position of the inequalities of basic map "bmap_i" |
| 95 | * (also represented by "tab_i", if not NULL) with respect to the basic map |
| 96 | * represented by "tab_j". |
| 97 | */ |
| 98 | static int *ineq_status_in(__isl_keep isl_basic_map *bmap_i, |
| 99 | struct isl_tab *tab_i, struct isl_tab *tab_j) |
| 100 | { |
| 101 | int k; |
| 102 | unsigned n_eq = bmap_i->n_eq; |
| 103 | int *ineq = isl_calloc_array(bmap_i->ctx, int, bmap_i->n_ineq)((int *)isl_calloc_or_die(bmap_i->ctx, bmap_i->n_ineq, sizeof (int))); |
| 104 | |
| 105 | if (!ineq) |
| 106 | return NULL((void*)0); |
| 107 | |
| 108 | for (k = 0; k < bmap_i->n_ineq; ++k) { |
| 109 | if (tab_i && isl_tab_is_redundant(tab_i, n_eq + k)) { |
| 110 | ineq[k] = STATUS_REDUNDANT1; |
| 111 | continue; |
| 112 | } |
| 113 | ineq[k] = status_in(bmap_i->ineq[k], tab_j); |
| 114 | if (ineq[k] == STATUS_ERROR-1) |
| 115 | goto error; |
| 116 | if (ineq[k] == STATUS_SEPARATE3) |
| 117 | break; |
| 118 | } |
| 119 | |
| 120 | return ineq; |
| 121 | error: |
| 122 | free(ineq); |
| 123 | return NULL((void*)0); |
| 124 | } |
| 125 | |
| 126 | static int any(int *con, unsigned len, int status) |
| 127 | { |
| 128 | int i; |
| 129 | |
| 130 | for (i = 0; i < len ; ++i) |
| 131 | if (con[i] == status) |
| 132 | return 1; |
| 133 | return 0; |
| 134 | } |
| 135 | |
| 136 | /* Return the first position of "status" in the list "con" of length "len". |
| 137 | * Return -1 if there is no such entry. |
| 138 | */ |
| 139 | static int find(int *con, unsigned len, int status) |
| 140 | { |
| 141 | int i; |
| 142 | |
| 143 | for (i = 0; i < len ; ++i) |
| 144 | if (con[i] == status) |
| 145 | return i; |
| 146 | return -1; |
| 147 | } |
| 148 | |
| 149 | static int count(int *con, unsigned len, int status) |
| 150 | { |
| 151 | int i; |
| 152 | int c = 0; |
| 153 | |
| 154 | for (i = 0; i < len ; ++i) |
| 155 | if (con[i] == status) |
| 156 | c++; |
| 157 | return c; |
| 158 | } |
| 159 | |
| 160 | static int all(int *con, unsigned len, int status) |
| 161 | { |
| 162 | int i; |
| 163 | |
| 164 | for (i = 0; i < len ; ++i) { |
| 165 | if (con[i] == STATUS_REDUNDANT1) |
| 166 | continue; |
| 167 | if (con[i] != status) |
| 168 | return 0; |
| 169 | } |
| 170 | return 1; |
| 171 | } |
| 172 | |
| 173 | /* Internal information associated to a basic map in a map |
| 174 | * that is to be coalesced by isl_map_coalesce. |
| 175 | * |
| 176 | * "bmap" is the basic map itself (or NULL if "removed" is set) |
| 177 | * "tab" is the corresponding tableau (or NULL if "removed" is set) |
| 178 | * "hull_hash" identifies the affine space in which "bmap" lives. |
| 179 | * "removed" is set if this basic map has been removed from the map |
| 180 | * "simplify" is set if this basic map may have some unknown integer |
| 181 | * divisions that were not present in the input basic maps. The basic |
| 182 | * map should then be simplified such that we may be able to find |
| 183 | * a definition among the constraints. |
| 184 | * |
| 185 | * "eq" and "ineq" are only set if we are currently trying to coalesce |
| 186 | * this basic map with another basic map, in which case they represent |
| 187 | * the position of the inequalities of this basic map with respect to |
| 188 | * the other basic map. The number of elements in the "eq" array |
| 189 | * is twice the number of equalities in the "bmap", corresponding |
| 190 | * to the two inequalities that make up each equality. |
| 191 | */ |
| 192 | struct isl_coalesce_info { |
| 193 | isl_basic_map *bmap; |
| 194 | struct isl_tab *tab; |
| 195 | uint32_t hull_hash; |
| 196 | int removed; |
| 197 | int simplify; |
| 198 | int *eq; |
| 199 | int *ineq; |
| 200 | }; |
| 201 | |
| 202 | /* Are all non-redundant constraints of the basic map represented by "info" |
| 203 | * either valid or cut constraints with respect to the other basic map? |
| 204 | */ |
| 205 | static int all_valid_or_cut(struct isl_coalesce_info *info) |
| 206 | { |
| 207 | int i; |
| 208 | |
| 209 | for (i = 0; i < 2 * info->bmap->n_eq; ++i) { |
| 210 | if (info->eq[i] == STATUS_REDUNDANT1) |
| 211 | continue; |
| 212 | if (info->eq[i] == STATUS_VALID2) |
| 213 | continue; |
| 214 | if (info->eq[i] == STATUS_CUT4) |
| 215 | continue; |
| 216 | return 0; |
| 217 | } |
| 218 | |
| 219 | for (i = 0; i < info->bmap->n_ineq; ++i) { |
| 220 | if (info->ineq[i] == STATUS_REDUNDANT1) |
| 221 | continue; |
| 222 | if (info->ineq[i] == STATUS_VALID2) |
| 223 | continue; |
| 224 | if (info->ineq[i] == STATUS_CUT4) |
| 225 | continue; |
| 226 | return 0; |
| 227 | } |
| 228 | |
| 229 | return 1; |
| 230 | } |
| 231 | |
| 232 | /* Compute the hash of the (apparent) affine hull of info->bmap (with |
| 233 | * the existentially quantified variables removed) and store it |
| 234 | * in info->hash. |
| 235 | */ |
| 236 | static int coalesce_info_set_hull_hash(struct isl_coalesce_info *info) |
| 237 | { |
| 238 | isl_basic_map *hull; |
| 239 | unsigned n_div; |
| 240 | |
| 241 | hull = isl_basic_map_copy(info->bmap); |
| 242 | hull = isl_basic_map_plain_affine_hull(hull); |
| 243 | n_div = isl_basic_map_dim(hull, isl_dim_div); |
| 244 | hull = isl_basic_map_drop_constraints_involving_dims(hull, |
| 245 | isl_dim_div, 0, n_div); |
| 246 | info->hull_hash = isl_basic_map_get_hash(hull); |
| 247 | isl_basic_map_free(hull); |
| 248 | |
| 249 | return hull ? 0 : -1; |
| 250 | } |
| 251 | |
| 252 | /* Free all the allocated memory in an array |
| 253 | * of "n" isl_coalesce_info elements. |
| 254 | */ |
| 255 | static void clear_coalesce_info(int n, struct isl_coalesce_info *info) |
| 256 | { |
| 257 | int i; |
| 258 | |
| 259 | if (!info) |
| 260 | return; |
| 261 | |
| 262 | for (i = 0; i < n; ++i) { |
| 263 | isl_basic_map_free(info[i].bmap); |
| 264 | isl_tab_free(info[i].tab); |
| 265 | } |
| 266 | |
| 267 | free(info); |
| 268 | } |
| 269 | |
| 270 | /* Drop the basic map represented by "info". |
| 271 | * That is, clear the memory associated to the entry and |
| 272 | * mark it as having been removed. |
| 273 | */ |
| 274 | static void drop(struct isl_coalesce_info *info) |
| 275 | { |
| 276 | info->bmap = isl_basic_map_free(info->bmap); |
| 277 | isl_tab_free(info->tab); |
| 278 | info->tab = NULL((void*)0); |
| 279 | info->removed = 1; |
| 280 | } |
| 281 | |
| 282 | /* Exchange the information in "info1" with that in "info2". |
| 283 | */ |
| 284 | static void exchange(struct isl_coalesce_info *info1, |
| 285 | struct isl_coalesce_info *info2) |
| 286 | { |
| 287 | struct isl_coalesce_info info; |
| 288 | |
| 289 | info = *info1; |
| 290 | *info1 = *info2; |
| 291 | *info2 = info; |
| 292 | } |
| 293 | |
| 294 | /* This type represents the kind of change that has been performed |
| 295 | * while trying to coalesce two basic maps. |
| 296 | * |
| 297 | * isl_change_none: nothing was changed |
| 298 | * isl_change_drop_first: the first basic map was removed |
| 299 | * isl_change_drop_second: the second basic map was removed |
| 300 | * isl_change_fuse: the two basic maps were replaced by a new basic map. |
| 301 | */ |
| 302 | enum isl_change { |
| 303 | isl_change_error = -1, |
| 304 | isl_change_none = 0, |
| 305 | isl_change_drop_first, |
| 306 | isl_change_drop_second, |
| 307 | isl_change_fuse, |
| 308 | }; |
| 309 | |
| 310 | /* Update "change" based on an interchange of the first and the second |
| 311 | * basic map. That is, interchange isl_change_drop_first and |
| 312 | * isl_change_drop_second. |
| 313 | */ |
| 314 | static enum isl_change invert_change(enum isl_change change) |
| 315 | { |
| 316 | switch (change) { |
| 317 | case isl_change_error: |
| 318 | return isl_change_error; |
| 319 | case isl_change_none: |
| 320 | return isl_change_none; |
| 321 | case isl_change_drop_first: |
| 322 | return isl_change_drop_second; |
| 323 | case isl_change_drop_second: |
| 324 | return isl_change_drop_first; |
| 325 | case isl_change_fuse: |
| 326 | return isl_change_fuse; |
| 327 | } |
| 328 | |
| 329 | return isl_change_error; |
| 330 | } |
| 331 | |
| 332 | /* Add the valid constraints of the basic map represented by "info" |
| 333 | * to "bmap". "len" is the size of the constraints. |
| 334 | * If only one of the pair of inequalities that make up an equality |
| 335 | * is valid, then add that inequality. |
| 336 | */ |
| 337 | static __isl_give isl_basic_map *add_valid_constraints( |
| 338 | __isl_take isl_basic_map *bmap, struct isl_coalesce_info *info, |
| 339 | unsigned len) |
| 340 | { |
| 341 | int k, l; |
| 342 | |
| 343 | if (!bmap) |
| 344 | return NULL((void*)0); |
| 345 | |
| 346 | for (k = 0; k < info->bmap->n_eq; ++k) { |
| 347 | if (info->eq[2 * k] == STATUS_VALID2 && |
| 348 | info->eq[2 * k + 1] == STATUS_VALID2) { |
| 349 | l = isl_basic_map_alloc_equality(bmap); |
| 350 | if (l < 0) |
| 351 | return isl_basic_map_free(bmap); |
| 352 | isl_seq_cpy(bmap->eq[l], info->bmap->eq[k], len); |
| 353 | } else if (info->eq[2 * k] == STATUS_VALID2) { |
| 354 | l = isl_basic_map_alloc_inequality(bmap); |
| 355 | if (l < 0) |
| 356 | return isl_basic_map_free(bmap); |
| 357 | isl_seq_neg(bmap->ineq[l], info->bmap->eq[k], len); |
| 358 | } else if (info->eq[2 * k + 1] == STATUS_VALID2) { |
| 359 | l = isl_basic_map_alloc_inequality(bmap); |
| 360 | if (l < 0) |
| 361 | return isl_basic_map_free(bmap); |
| 362 | isl_seq_cpy(bmap->ineq[l], info->bmap->eq[k], len); |
| 363 | } |
| 364 | } |
| 365 | |
| 366 | for (k = 0; k < info->bmap->n_ineq; ++k) { |
| 367 | if (info->ineq[k] != STATUS_VALID2) |
| 368 | continue; |
| 369 | l = isl_basic_map_alloc_inequality(bmap); |
| 370 | if (l < 0) |
| 371 | return isl_basic_map_free(bmap); |
| 372 | isl_seq_cpy(bmap->ineq[l], info->bmap->ineq[k], len); |
| 373 | } |
| 374 | |
| 375 | return bmap; |
| 376 | } |
| 377 | |
| 378 | /* Is "bmap" defined by a number of (non-redundant) constraints that |
| 379 | * is greater than the number of constraints of basic maps i and j combined? |
| 380 | * Equalities are counted as two inequalities. |
| 381 | */ |
| 382 | static int number_of_constraints_increases(int i, int j, |
| 383 | struct isl_coalesce_info *info, |
| 384 | __isl_keep isl_basic_map *bmap, struct isl_tab *tab) |
| 385 | { |
| 386 | int k, n_old, n_new; |
| 387 | |
| 388 | n_old = 2 * info[i].bmap->n_eq + info[i].bmap->n_ineq; |
| 389 | n_old += 2 * info[j].bmap->n_eq + info[j].bmap->n_ineq; |
| 390 | |
| 391 | n_new = 2 * bmap->n_eq; |
| 392 | for (k = 0; k < bmap->n_ineq; ++k) |
| 393 | if (!isl_tab_is_redundant(tab, bmap->n_eq + k)) |
| 394 | ++n_new; |
| 395 | |
| 396 | return n_new > n_old; |
| 397 | } |
| 398 | |
| 399 | /* Replace the pair of basic maps i and j by the basic map bounded |
| 400 | * by the valid constraints in both basic maps and the constraints |
| 401 | * in extra (if not NULL). |
| 402 | * Place the fused basic map in the position that is the smallest of i and j. |
| 403 | * |
| 404 | * If "detect_equalities" is set, then look for equalities encoded |
| 405 | * as pairs of inequalities. |
| 406 | * If "check_number" is set, then the original basic maps are only |
| 407 | * replaced if the total number of constraints does not increase. |
| 408 | * While the number of integer divisions in the two basic maps |
| 409 | * is assumed to be the same, the actual definitions may be different. |
| 410 | * We only copy the definition from one of the basic map if it is |
| 411 | * the same as that of the other basic map. Otherwise, we mark |
| 412 | * the integer division as unknown and simplify the basic map |
| 413 | * in an attempt to recover the integer division definition. |
| 414 | */ |
| 415 | static enum isl_change fuse(int i, int j, struct isl_coalesce_info *info, |
| 416 | __isl_keep isl_mat *extra, int detect_equalities, int check_number) |
| 417 | { |
| 418 | int k, l; |
| 419 | struct isl_basic_map *fused = NULL((void*)0); |
| 420 | struct isl_tab *fused_tab = NULL((void*)0); |
| 421 | unsigned total = isl_basic_map_total_dim(info[i].bmap); |
| 422 | unsigned extra_rows = extra ? extra->n_row : 0; |
| 423 | unsigned n_eq, n_ineq; |
| 424 | int simplify = 0; |
| 425 | |
| 426 | if (j < i) |
| 427 | return fuse(j, i, info, extra, detect_equalities, check_number); |
| 428 | |
| 429 | n_eq = info[i].bmap->n_eq + info[j].bmap->n_eq; |
| 430 | n_ineq = info[i].bmap->n_ineq + info[j].bmap->n_ineq; |
| 431 | fused = isl_basic_map_alloc_space(isl_space_copy(info[i].bmap->dim), |
| 432 | info[i].bmap->n_div, n_eq, n_eq + n_ineq + extra_rows); |
| 433 | fused = add_valid_constraints(fused, &info[i], 1 + total); |
| 434 | fused = add_valid_constraints(fused, &info[j], 1 + total); |
| 435 | if (!fused) |
| 436 | goto error; |
| 437 | if (ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_RATIONAL)(!!(((info[i].bmap)->flags) & ((1 << 4)))) && |
| 438 | ISL_F_ISSET(info[j].bmap, ISL_BASIC_MAP_RATIONAL)(!!(((info[j].bmap)->flags) & ((1 << 4))))) |
| 439 | ISL_F_SET(fused, ISL_BASIC_MAP_RATIONAL)(((fused)->flags) |= ((1 << 4))); |
| 440 | |
| 441 | for (k = 0; k < info[i].bmap->n_div; ++k) { |
| 442 | int l = isl_basic_map_alloc_div(fused); |
| 443 | if (l < 0) |
| 444 | goto error; |
| 445 | if (isl_seq_eq(info[i].bmap->div[k], info[j].bmap->div[k], |
| 446 | 1 + 1 + total)) { |
| 447 | isl_seq_cpy(fused->div[l], info[i].bmap->div[k], |
| 448 | 1 + 1 + total); |
| 449 | } else { |
| 450 | isl_int_set_si(fused->div[l][0], 0)isl_sioimath_set_si((fused->div[l][0]), 0); |
| 451 | simplify = 1; |
| 452 | } |
| 453 | } |
| 454 | |
| 455 | for (k = 0; k < extra_rows; ++k) { |
| 456 | l = isl_basic_map_alloc_inequality(fused); |
| 457 | if (l < 0) |
| 458 | goto error; |
| 459 | isl_seq_cpy(fused->ineq[l], extra->row[k], 1 + total); |
| 460 | } |
| 461 | |
| 462 | if (detect_equalities) |
| 463 | fused = isl_basic_map_detect_inequality_pairs(fused, NULL((void*)0)); |
| 464 | fused = isl_basic_map_gauss(fused, NULL((void*)0)); |
| 465 | if (simplify || info[j].simplify) { |
| 466 | fused = isl_basic_map_simplify(fused); |
| 467 | info[i].simplify = 0; |
| 468 | } |
| 469 | fused = isl_basic_map_finalize(fused); |
| 470 | |
| 471 | fused_tab = isl_tab_from_basic_map(fused, 0); |
| 472 | if (isl_tab_detect_redundant(fused_tab) < 0) |
| 473 | goto error; |
| 474 | |
| 475 | if (check_number && |
| 476 | number_of_constraints_increases(i, j, info, fused, fused_tab)) { |
| 477 | isl_tab_free(fused_tab); |
| 478 | isl_basic_map_free(fused); |
| 479 | return isl_change_none; |
| 480 | } |
| 481 | |
| 482 | isl_basic_map_free(info[i].bmap); |
| 483 | info[i].bmap = fused; |
| 484 | isl_tab_free(info[i].tab); |
| 485 | info[i].tab = fused_tab; |
| 486 | drop(&info[j]); |
| 487 | |
| 488 | return isl_change_fuse; |
| 489 | error: |
| 490 | isl_tab_free(fused_tab); |
| 491 | isl_basic_map_free(fused); |
| 492 | return isl_change_error; |
| 493 | } |
| 494 | |
| 495 | /* Given a pair of basic maps i and j such that all constraints are either |
| 496 | * "valid" or "cut", check if the facets corresponding to the "cut" |
| 497 | * constraints of i lie entirely within basic map j. |
| 498 | * If so, replace the pair by the basic map consisting of the valid |
| 499 | * constraints in both basic maps. |
| 500 | * Checking whether the facet lies entirely within basic map j |
| 501 | * is performed by checking whether the constraints of basic map j |
| 502 | * are valid for the facet. These tests are performed on a rational |
| 503 | * tableau to avoid the theoretical possibility that a constraint |
| 504 | * that was considered to be a cut constraint for the entire basic map i |
| 505 | * happens to be considered to be a valid constraint for the facet, |
| 506 | * even though it cuts off the same rational points. |
| 507 | * |
| 508 | * To see that we are not introducing any extra points, call the |
| 509 | * two basic maps A and B and the resulting map U and let x |
| 510 | * be an element of U \setminus ( A \cup B ). |
| 511 | * A line connecting x with an element of A \cup B meets a facet F |
| 512 | * of either A or B. Assume it is a facet of B and let c_1 be |
| 513 | * the corresponding facet constraint. We have c_1(x) < 0 and |
| 514 | * so c_1 is a cut constraint. This implies that there is some |
| 515 | * (possibly rational) point x' satisfying the constraints of A |
| 516 | * and the opposite of c_1 as otherwise c_1 would have been marked |
| 517 | * valid for A. The line connecting x and x' meets a facet of A |
| 518 | * in a (possibly rational) point that also violates c_1, but this |
| 519 | * is impossible since all cut constraints of B are valid for all |
| 520 | * cut facets of A. |
| 521 | * In case F is a facet of A rather than B, then we can apply the |
| 522 | * above reasoning to find a facet of B separating x from A \cup B first. |
| 523 | */ |
| 524 | static enum isl_change check_facets(int i, int j, |
| 525 | struct isl_coalesce_info *info) |
| 526 | { |
| 527 | int k, l; |
| 528 | struct isl_tab_undo *snap, *snap2; |
| 529 | unsigned n_eq = info[i].bmap->n_eq; |
| 530 | |
| 531 | snap = isl_tab_snap(info[i].tab); |
| 532 | if (isl_tab_mark_rational(info[i].tab) < 0) |
| 533 | return isl_change_error; |
| 534 | snap2 = isl_tab_snap(info[i].tab); |
| 535 | |
| 536 | for (k = 0; k < info[i].bmap->n_ineq; ++k) { |
| 537 | if (info[i].ineq[k] != STATUS_CUT4) |
| 538 | continue; |
| 539 | if (isl_tab_select_facet(info[i].tab, n_eq + k) < 0) |
| 540 | return isl_change_error; |
| 541 | for (l = 0; l < info[j].bmap->n_ineq; ++l) { |
| 542 | int stat; |
| 543 | if (info[j].ineq[l] != STATUS_CUT4) |
| 544 | continue; |
| 545 | stat = status_in(info[j].bmap->ineq[l], info[i].tab); |
| 546 | if (stat < 0) |
| 547 | return isl_change_error; |
| 548 | if (stat != STATUS_VALID2) |
| 549 | break; |
| 550 | } |
| 551 | if (isl_tab_rollback(info[i].tab, snap2) < 0) |
| 552 | return isl_change_error; |
| 553 | if (l < info[j].bmap->n_ineq) |
| 554 | break; |
| 555 | } |
| 556 | |
| 557 | if (k < info[i].bmap->n_ineq) { |
| 558 | if (isl_tab_rollback(info[i].tab, snap) < 0) |
| 559 | return isl_change_error; |
| 560 | return isl_change_none; |
| 561 | } |
| 562 | return fuse(i, j, info, NULL((void*)0), 0, 0); |
| 563 | } |
| 564 | |
| 565 | /* Check if info->bmap contains the basic map represented |
| 566 | * by the tableau "tab". |
| 567 | * For each equality, we check both the constraint itself |
| 568 | * (as an inequality) and its negation. Make sure the |
| 569 | * equality is returned to its original state before returning. |
| 570 | */ |
| 571 | static int contains(struct isl_coalesce_info *info, struct isl_tab *tab) |
| 572 | { |
| 573 | int k; |
| 574 | unsigned dim; |
| 575 | isl_basic_map *bmap = info->bmap; |
| 576 | |
| 577 | dim = isl_basic_map_total_dim(bmap); |
| 578 | for (k = 0; k < bmap->n_eq; ++k) { |
| 579 | int stat; |
| 580 | isl_seq_neg(bmap->eq[k], bmap->eq[k], 1 + dim); |
| 581 | stat = status_in(bmap->eq[k], tab); |
| 582 | isl_seq_neg(bmap->eq[k], bmap->eq[k], 1 + dim); |
| 583 | if (stat < 0) |
| 584 | return -1; |
| 585 | if (stat != STATUS_VALID2) |
| 586 | return 0; |
| 587 | stat = status_in(bmap->eq[k], tab); |
| 588 | if (stat < 0) |
| 589 | return -1; |
| 590 | if (stat != STATUS_VALID2) |
| 591 | return 0; |
| 592 | } |
| 593 | |
| 594 | for (k = 0; k < bmap->n_ineq; ++k) { |
| 595 | int stat; |
| 596 | if (info->ineq[k] == STATUS_REDUNDANT1) |
| 597 | continue; |
| 598 | stat = status_in(bmap->ineq[k], tab); |
| 599 | if (stat < 0) |
| 600 | return -1; |
| 601 | if (stat != STATUS_VALID2) |
| 602 | return 0; |
| 603 | } |
| 604 | return 1; |
| 605 | } |
| 606 | |
| 607 | /* Basic map "i" has an inequality (say "k") that is adjacent |
| 608 | * to some inequality of basic map "j". All the other inequalities |
| 609 | * are valid for "j". |
| 610 | * Check if basic map "j" forms an extension of basic map "i". |
| 611 | * |
| 612 | * Note that this function is only called if some of the equalities or |
| 613 | * inequalities of basic map "j" do cut basic map "i". The function is |
| 614 | * correct even if there are no such cut constraints, but in that case |
| 615 | * the additional checks performed by this function are overkill. |
| 616 | * |
| 617 | * In particular, we replace constraint k, say f >= 0, by constraint |
| 618 | * f <= -1, add the inequalities of "j" that are valid for "i" |
| 619 | * and check if the result is a subset of basic map "j". |
| 620 | * To improve the chances of the subset relation being detected, |
| 621 | * any variable that only attains a single integer value |
| 622 | * in the tableau of "i" is first fixed to that value. |
| 623 | * If the result is a subset, then we know that this result is exactly equal |
| 624 | * to basic map "j" since all its constraints are valid for basic map "j". |
| 625 | * By combining the valid constraints of "i" (all equalities and all |
| 626 | * inequalities except "k") and the valid constraints of "j" we therefore |
| 627 | * obtain a basic map that is equal to their union. |
| 628 | * In this case, there is no need to perform a rollback of the tableau |
| 629 | * since it is going to be destroyed in fuse(). |
| 630 | * |
| 631 | * |
| 632 | * |\__ |\__ |
| 633 | * | \__ | \__ |
| 634 | * | \_ => | \__ |
| 635 | * |_______| _ |_________\ |
| 636 | * |
| 637 | * |
| 638 | * |\ |\ |
| 639 | * | \ | \ |
| 640 | * | \ | \ |
| 641 | * | | | \ |
| 642 | * | ||\ => | \ |
| 643 | * | || \ | \ |
| 644 | * | || | | | |
| 645 | * |__||_/ |_____/ |
| 646 | */ |
| 647 | static enum isl_change is_adj_ineq_extension(int i, int j, |
| 648 | struct isl_coalesce_info *info) |
| 649 | { |
| 650 | int k; |
| 651 | struct isl_tab_undo *snap; |
| 652 | unsigned n_eq = info[i].bmap->n_eq; |
| 653 | unsigned total = isl_basic_map_total_dim(info[i].bmap); |
| 654 | int r; |
| 655 | int super; |
| 656 | |
| 657 | if (isl_tab_extend_cons(info[i].tab, 1 + info[j].bmap->n_ineq) < 0) |
| 658 | return isl_change_error; |
| 659 | |
| 660 | k = find(info[i].ineq, info[i].bmap->n_ineq, STATUS_ADJ_INEQ6); |
| 661 | if (k < 0) |
| 662 | isl_die(isl_basic_map_get_ctx(info[i].bmap), isl_error_internal,do { isl_handle_error(isl_basic_map_get_ctx(info[i].bmap), isl_error_internal , "info[i].ineq should have exactly one STATUS_ADJ_INEQ", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn295388/tools/polly/lib/External/isl/isl_coalesce.c" , 664); return isl_change_error; } while (0) |
| 663 | "info[i].ineq should have exactly one STATUS_ADJ_INEQ",do { isl_handle_error(isl_basic_map_get_ctx(info[i].bmap), isl_error_internal , "info[i].ineq should have exactly one STATUS_ADJ_INEQ", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn295388/tools/polly/lib/External/isl/isl_coalesce.c" , 664); return isl_change_error; } while (0) |
| 664 | return isl_change_error)do { isl_handle_error(isl_basic_map_get_ctx(info[i].bmap), isl_error_internal , "info[i].ineq should have exactly one STATUS_ADJ_INEQ", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn295388/tools/polly/lib/External/isl/isl_coalesce.c" , 664); return isl_change_error; } while (0); |
| 665 | |
| 666 | snap = isl_tab_snap(info[i].tab); |
| 667 | |
| 668 | if (isl_tab_unrestrict(info[i].tab, n_eq + k) < 0) |
| 669 | return isl_change_error; |
| 670 | |
| 671 | isl_seq_neg(info[i].bmap->ineq[k], info[i].bmap->ineq[k], 1 + total); |
| 672 | isl_int_sub_ui(info[i].bmap->ineq[k][0], info[i].bmap->ineq[k][0], 1)isl_sioimath_sub_ui((info[i].bmap->ineq[k][0]), *(info[i]. bmap->ineq[k][0]), 1); |
| 673 | r = isl_tab_add_ineq(info[i].tab, info[i].bmap->ineq[k]); |
| 674 | isl_seq_neg(info[i].bmap->ineq[k], info[i].bmap->ineq[k], 1 + total); |
| 675 | isl_int_sub_ui(info[i].bmap->ineq[k][0], info[i].bmap->ineq[k][0], 1)isl_sioimath_sub_ui((info[i].bmap->ineq[k][0]), *(info[i]. bmap->ineq[k][0]), 1); |
| 676 | if (r < 0) |
| 677 | return isl_change_error; |
| 678 | |
| 679 | for (k = 0; k < info[j].bmap->n_ineq; ++k) { |
| 680 | if (info[j].ineq[k] != STATUS_VALID2) |
| 681 | continue; |
| 682 | if (isl_tab_add_ineq(info[i].tab, info[j].bmap->ineq[k]) < 0) |
| 683 | return isl_change_error; |
| 684 | } |
| 685 | if (isl_tab_detect_constants(info[i].tab) < 0) |
| 686 | return isl_change_error; |
| 687 | |
| 688 | super = contains(&info[j], info[i].tab); |
| 689 | if (super < 0) |
| 690 | return isl_change_error; |
| 691 | if (super) |
| 692 | return fuse(i, j, info, NULL((void*)0), 0, 0); |
| 693 | |
| 694 | if (isl_tab_rollback(info[i].tab, snap) < 0) |
| 695 | return isl_change_error; |
| 696 | |
| 697 | return isl_change_none; |
| 698 | } |
| 699 | |
| 700 | |
| 701 | /* Both basic maps have at least one inequality with and adjacent |
| 702 | * (but opposite) inequality in the other basic map. |
| 703 | * Check that there are no cut constraints and that there is only |
| 704 | * a single pair of adjacent inequalities. |
| 705 | * If so, we can replace the pair by a single basic map described |
| 706 | * by all but the pair of adjacent inequalities. |
| 707 | * Any additional points introduced lie strictly between the two |
| 708 | * adjacent hyperplanes and can therefore be integral. |
| 709 | * |
| 710 | * ____ _____ |
| 711 | * / ||\ / \ |
| 712 | * / || \ / \ |
| 713 | * \ || \ => \ \ |
| 714 | * \ || / \ / |
| 715 | * \___||_/ \_____/ |
| 716 | * |
| 717 | * The test for a single pair of adjancent inequalities is important |
| 718 | * for avoiding the combination of two basic maps like the following |
| 719 | * |
| 720 | * /| |
| 721 | * / | |
| 722 | * /__| |
| 723 | * _____ |
| 724 | * | | |
| 725 | * | | |
| 726 | * |___| |
| 727 | * |
| 728 | * If there are some cut constraints on one side, then we may |
| 729 | * still be able to fuse the two basic maps, but we need to perform |
| 730 | * some additional checks in is_adj_ineq_extension. |
| 731 | */ |
| 732 | static enum isl_change check_adj_ineq(int i, int j, |
| 733 | struct isl_coalesce_info *info) |
| 734 | { |
| 735 | int count_i, count_j; |
| 736 | int cut_i, cut_j; |
| 737 | |
| 738 | count_i = count(info[i].ineq, info[i].bmap->n_ineq, STATUS_ADJ_INEQ6); |
| 739 | count_j = count(info[j].ineq, info[j].bmap->n_ineq, STATUS_ADJ_INEQ6); |
| 740 | |
| 741 | if (count_i != 1 && count_j != 1) |
| 742 | return isl_change_none; |
| 743 | |
| 744 | cut_i = any(info[i].eq, 2 * info[i].bmap->n_eq, STATUS_CUT4) || |
| 745 | any(info[i].ineq, info[i].bmap->n_ineq, STATUS_CUT4); |
| 746 | cut_j = any(info[j].eq, 2 * info[j].bmap->n_eq, STATUS_CUT4) || |
| 747 | any(info[j].ineq, info[j].bmap->n_ineq, STATUS_CUT4); |
| 748 | |
| 749 | if (!cut_i && !cut_j && count_i == 1 && count_j == 1) |
| 750 | return fuse(i, j, info, NULL((void*)0), 0, 0); |
| 751 | |
| 752 | if (count_i == 1 && !cut_i) |
| 753 | return is_adj_ineq_extension(i, j, info); |
| 754 | |
| 755 | if (count_j == 1 && !cut_j) |
| 756 | return is_adj_ineq_extension(j, i, info); |
| 757 | |
| 758 | return isl_change_none; |
| 759 | } |
| 760 | |
| 761 | /* Given an affine transformation matrix "T", does row "row" represent |
| 762 | * anything other than a unit vector (possibly shifted by a constant) |
| 763 | * that is not involved in any of the other rows? |
| 764 | * |
| 765 | * That is, if a constraint involves the variable corresponding to |
| 766 | * the row, then could its preimage by "T" have any coefficients |
| 767 | * that are different from those in the original constraint? |
| 768 | */ |
| 769 | static int not_unique_unit_row(__isl_keep isl_mat *T, int row) |
| 770 | { |
| 771 | int i, j; |
| 772 | int len = T->n_col - 1; |
| 773 | |
| 774 | i = isl_seq_first_non_zero(T->row[row] + 1, len); |
| 775 | if (i < 0) |
| 776 | return 1; |
| 777 | if (!isl_int_is_one(T->row[row][1 + i])(isl_sioimath_cmp_si(*(T->row[row][1 + i]), 1) == 0) && |
| 778 | !isl_int_is_negone(T->row[row][1 + i])(isl_sioimath_cmp_si(*(T->row[row][1 + i]), -1) == 0)) |
| 779 | return 1; |
| 780 | |
| 781 | j = isl_seq_first_non_zero(T->row[row] + 1 + i + 1, len - (i + 1)); |
| 782 | if (j >= 0) |
| 783 | return 1; |
| 784 | |
| 785 | for (j = 1; j < T->n_row; ++j) { |
| 786 | if (j == row) |
| 787 | continue; |
| 788 | if (!isl_int_is_zero(T->row[j][1 + i])(isl_sioimath_sgn(*(T->row[j][1 + i])) == 0)) |
| 789 | return 1; |
| 790 | } |
| 791 | |
| 792 | return 0; |
| 793 | } |
| 794 | |
| 795 | /* Does inequality constraint "ineq" of "bmap" involve any of |
| 796 | * the variables marked in "affected"? |
| 797 | * "total" is the total number of variables, i.e., the number |
| 798 | * of entries in "affected". |
| 799 | */ |
| 800 | static int is_affected(__isl_keep isl_basic_map *bmap, int ineq, int *affected, |
| 801 | int total) |
| 802 | { |
| 803 | int i; |
| 804 | |
| 805 | for (i = 0; i < total; ++i) { |
| 806 | if (!affected[i]) |
| 807 | continue; |
| 808 | if (!isl_int_is_zero(bmap->ineq[ineq][1 + i])(isl_sioimath_sgn(*(bmap->ineq[ineq][1 + i])) == 0)) |
| 809 | return 1; |
| 810 | } |
| 811 | |
| 812 | return 0; |
| 813 | } |
| 814 | |
| 815 | /* Given the compressed version of inequality constraint "ineq" |
| 816 | * of info->bmap in "v", check if the constraint can be tightened, |
| 817 | * where the compression is based on an equality constraint valid |
| 818 | * for info->tab. |
| 819 | * If so, add the tightened version of the inequality constraint |
| 820 | * to info->tab. "v" may be modified by this function. |
| 821 | * |
| 822 | * That is, if the compressed constraint is of the form |
| 823 | * |
| 824 | * m f() + c >= 0 |
| 825 | * |
| 826 | * with 0 < c < m, then it is equivalent to |
| 827 | * |
| 828 | * f() >= 0 |
| 829 | * |
| 830 | * This means that c can also be subtracted from the original, |
| 831 | * uncompressed constraint without affecting the integer points |
| 832 | * in info->tab. Add this tightened constraint as an extra row |
| 833 | * to info->tab to make this information explicitly available. |
| 834 | */ |
| 835 | static __isl_give isl_vec *try_tightening(struct isl_coalesce_info *info, |
| 836 | int ineq, __isl_take isl_vec *v) |
| 837 | { |
| 838 | isl_ctx *ctx; |
| 839 | int r; |
| 840 | |
| 841 | if (!v) |
| 842 | return NULL((void*)0); |
| 843 | |
| 844 | ctx = isl_vec_get_ctx(v); |
| 845 | isl_seq_gcd(v->el + 1, v->size - 1, &ctx->normalize_gcd); |
| 846 | if (isl_int_is_zero(ctx->normalize_gcd)(isl_sioimath_sgn(*(ctx->normalize_gcd)) == 0) || |
| 847 | isl_int_is_one(ctx->normalize_gcd)(isl_sioimath_cmp_si(*(ctx->normalize_gcd), 1) == 0)) { |
| 848 | return v; |
| 849 | } |
| 850 | |
| 851 | v = isl_vec_cow(v); |
| 852 | if (!v) |
| 853 | return NULL((void*)0); |
| 854 | |
| 855 | isl_int_fdiv_r(v->el[0], v->el[0], ctx->normalize_gcd)isl_sioimath_fdiv_r((v->el[0]), *(v->el[0]), *(ctx-> normalize_gcd)); |
| 856 | if (isl_int_is_zero(v->el[0])(isl_sioimath_sgn(*(v->el[0])) == 0)) |
| 857 | return v; |
| 858 | |
| 859 | if (isl_tab_extend_cons(info->tab, 1) < 0) |
| 860 | return isl_vec_free(v); |
| 861 | |
| 862 | isl_int_sub(info->bmap->ineq[ineq][0],isl_sioimath_sub((info->bmap->ineq[ineq][0]), *(info-> bmap->ineq[ineq][0]), *(v->el[0])) |
| 863 | info->bmap->ineq[ineq][0], v->el[0])isl_sioimath_sub((info->bmap->ineq[ineq][0]), *(info-> bmap->ineq[ineq][0]), *(v->el[0])); |
| 864 | r = isl_tab_add_ineq(info->tab, info->bmap->ineq[ineq]); |
| 865 | isl_int_add(info->bmap->ineq[ineq][0],isl_sioimath_add((info->bmap->ineq[ineq][0]), *(info-> bmap->ineq[ineq][0]), *(v->el[0])) |
| 866 | info->bmap->ineq[ineq][0], v->el[0])isl_sioimath_add((info->bmap->ineq[ineq][0]), *(info-> bmap->ineq[ineq][0]), *(v->el[0])); |
| 867 | |
| 868 | if (r < 0) |
| 869 | return isl_vec_free(v); |
| 870 | |
| 871 | return v; |
| 872 | } |
| 873 | |
| 874 | /* Tighten the (non-redundant) constraints on the facet represented |
| 875 | * by info->tab. |
| 876 | * In particular, on input, info->tab represents the result |
| 877 | * of relaxing the "n" inequality constraints of info->bmap in "relaxed" |
| 878 | * by one, i.e., replacing f_i >= 0 by f_i + 1 >= 0, and then |
| 879 | * replacing the one at index "l" by the corresponding equality, |
| 880 | * i.e., f_k + 1 = 0, with k = relaxed[l]. |
| 881 | * |
| 882 | * Compute a variable compression from the equality constraint f_k + 1 = 0 |
| 883 | * and use it to tighten the other constraints of info->bmap |
| 884 | * (that is, all constraints that have not been relaxed), |
| 885 | * updating info->tab (and leaving info->bmap untouched). |
| 886 | * The compression handles essentially two cases, one where a variable |
| 887 | * is assigned a fixed value and can therefore be eliminated, and one |
| 888 | * where one variable is a shifted multiple of some other variable and |
| 889 | * can therefore be replaced by that multiple. |
| 890 | * Gaussian elimination would also work for the first case, but for |
| 891 | * the second case, the effectiveness would depend on the order |
| 892 | * of the variables. |
| 893 | * After compression, some of the constraints may have coefficients |
| 894 | * with a common divisor. If this divisor does not divide the constant |
| 895 | * term, then the constraint can be tightened. |
| 896 | * The tightening is performed on the tableau info->tab by introducing |
| 897 | * extra (temporary) constraints. |
| 898 | * |
| 899 | * Only constraints that are possibly affected by the compression are |
| 900 | * considered. In particular, if the constraint only involves variables |
| 901 | * that are directly mapped to a distinct set of other variables, then |
| 902 | * no common divisor can be introduced and no tightening can occur. |
| 903 | * |
| 904 | * It is important to only consider the non-redundant constraints |
| 905 | * since the facet constraint has been relaxed prior to the call |
| 906 | * to this function, meaning that the constraints that were redundant |
| 907 | * prior to the relaxation may no longer be redundant. |
| 908 | * These constraints will be ignored in the fused result, so |
| 909 | * the fusion detection should not exploit them. |
| 910 | */ |
| 911 | static isl_stat tighten_on_relaxed_facet(struct isl_coalesce_info *info, |
| 912 | int n, int *relaxed, int l) |
| 913 | { |
| 914 | unsigned total; |
| 915 | isl_ctx *ctx; |
| 916 | isl_vec *v = NULL((void*)0); |
| 917 | isl_mat *T; |
| 918 | int i; |
| 919 | int k; |
| 920 | int *affected; |
| 921 | |
| 922 | k = relaxed[l]; |
| 923 | ctx = isl_basic_map_get_ctx(info->bmap); |
| 924 | total = isl_basic_map_total_dim(info->bmap); |
| 925 | isl_int_add_ui(info->bmap->ineq[k][0], info->bmap->ineq[k][0], 1)isl_sioimath_add_ui((info->bmap->ineq[k][0]), *(info-> bmap->ineq[k][0]), 1); |
| 926 | T = isl_mat_sub_alloc6(ctx, info->bmap->ineq, k, 1, 0, 1 + total); |
| 927 | T = isl_mat_variable_compression(T, NULL((void*)0)); |
| 928 | isl_int_sub_ui(info->bmap->ineq[k][0], info->bmap->ineq[k][0], 1)isl_sioimath_sub_ui((info->bmap->ineq[k][0]), *(info-> bmap->ineq[k][0]), 1); |
| 929 | if (!T) |
| 930 | return isl_stat_error; |
| 931 | if (T->n_col == 0) { |
| 932 | isl_mat_free(T); |
| 933 | return isl_stat_ok; |
| 934 | } |
| 935 | |
| 936 | affected = isl_alloc_array(ctx, int, total)((int *)isl_malloc_or_die(ctx, (total)*sizeof(int))); |
| 937 | if (!affected) |
| 938 | goto error; |
| 939 | |
| 940 | for (i = 0; i < total; ++i) |
| 941 | affected[i] = not_unique_unit_row(T, 1 + i); |
| 942 | |
| 943 | for (i = 0; i < info->bmap->n_ineq; ++i) { |
| 944 | if (any(relaxed, n, i)) |
| 945 | continue; |
| 946 | if (info->ineq[i] == STATUS_REDUNDANT1) |
| 947 | continue; |
| 948 | if (!is_affected(info->bmap, i, affected, total)) |
| 949 | continue; |
| 950 | v = isl_vec_alloc(ctx, 1 + total); |
| 951 | if (!v) |
| 952 | goto error; |
| 953 | isl_seq_cpy(v->el, info->bmap->ineq[i], 1 + total); |
| 954 | v = isl_vec_mat_product(v, isl_mat_copy(T)); |
| 955 | v = try_tightening(info, i, v); |
| 956 | isl_vec_free(v); |
| 957 | if (!v) |
| 958 | goto error; |
| 959 | } |
| 960 | |
| 961 | isl_mat_free(T); |
| 962 | free(affected); |
| 963 | return isl_stat_ok; |
| 964 | error: |
| 965 | isl_mat_free(T); |
| 966 | free(affected); |
| 967 | return isl_stat_error; |
| 968 | } |
| 969 | |
| 970 | /* Replace the basic maps "i" and "j" by an extension of "i" |
| 971 | * along the "n" inequality constraints in "relax" by one. |
| 972 | * The tableau info[i].tab has already been extended. |
| 973 | * Extend info[i].bmap accordingly by relaxing all constraints in "relax" |
| 974 | * by one. |
| 975 | * Each integer division that does not have exactly the same |
| 976 | * definition in "i" and "j" is marked unknown and the basic map |
| 977 | * is scheduled to be simplified in an attempt to recover |
| 978 | * the integer division definition. |
| 979 | * Place the extension in the position that is the smallest of i and j. |
| 980 | */ |
| 981 | static enum isl_change extend(int i, int j, int n, int *relax, |
| 982 | struct isl_coalesce_info *info) |
| 983 | { |
| 984 | int l; |
| 985 | unsigned total; |
| 986 | |
| 987 | info[i].bmap = isl_basic_map_cow(info[i].bmap); |
| 988 | if (!info[i].bmap) |
| 989 | return isl_change_error; |
| 990 | total = isl_basic_map_total_dim(info[i].bmap); |
| 991 | for (l = 0; l < info[i].bmap->n_div; ++l) |
| 992 | if (!isl_seq_eq(info[i].bmap->div[l], |
| 993 | info[j].bmap->div[l], 1 + 1 + total)) { |
| 994 | isl_int_set_si(info[i].bmap->div[l][0], 0)isl_sioimath_set_si((info[i].bmap->div[l][0]), 0); |
| 995 | info[i].simplify = 1; |
| 996 | } |
| 997 | for (l = 0; l < n; ++l) |
| 998 | isl_int_add_ui(info[i].bmap->ineq[relax[l]][0],isl_sioimath_add_ui((info[i].bmap->ineq[relax[l]][0]), *(info [i].bmap->ineq[relax[l]][0]), 1) |
| 999 | info[i].bmap->ineq[relax[l]][0], 1)isl_sioimath_add_ui((info[i].bmap->ineq[relax[l]][0]), *(info [i].bmap->ineq[relax[l]][0]), 1); |
| 1000 | ISL_F_SET(info[i].bmap, ISL_BASIC_MAP_FINAL)(((info[i].bmap)->flags) |= ((1 << 0))); |
| 1001 | drop(&info[j]); |
| 1002 | if (j < i) |
| 1003 | exchange(&info[i], &info[j]); |
| 1004 | return isl_change_fuse; |
| 1005 | } |
| 1006 | |
| 1007 | /* Basic map "i" has "n" inequality constraints (collected in "relax") |
| 1008 | * that are such that they include basic map "j" if they are relaxed |
| 1009 | * by one. All the other inequalities are valid for "j". |
| 1010 | * Check if basic map "j" forms an extension of basic map "i". |
| 1011 | * |
| 1012 | * In particular, relax the constraints in "relax", compute the corresponding |
| 1013 | * facets one by one and check whether each of these is included |
| 1014 | * in the other basic map. |
| 1015 | * Before testing for inclusion, the constraints on each facet |
| 1016 | * are tightened to increase the chance of an inclusion being detected. |
| 1017 | * (Adding the valid constraints of "j" to the tableau of "i", as is done |
| 1018 | * in is_adj_ineq_extension, may further increase those chances, but this |
| 1019 | * is not currently done.) |
| 1020 | * If each facet is included, we know that relaxing the constraints extends |
| 1021 | * the basic map with exactly the other basic map (we already know that this |
| 1022 | * other basic map is included in the extension, because all other |
| 1023 | * inequality constraints are valid of "j") and we can replace the |
| 1024 | * two basic maps by this extension. |
| 1025 | * ____ _____ |
| 1026 | * / || / | |
| 1027 | * / || / | |
| 1028 | * \ || => \ | |
| 1029 | * \ || \ | |
| 1030 | * \___|| \____| |
| 1031 | * |
| 1032 | * |
| 1033 | * \ |\ |
| 1034 | * |\\ | \ |
| 1035 | * | \\ | \ |
| 1036 | * | | => | / |
| 1037 | * | / | / |
| 1038 | * |/ |/ |
| 1039 | */ |
| 1040 | static enum isl_change is_relaxed_extension(int i, int j, int n, int *relax, |
| 1041 | struct isl_coalesce_info *info) |
| 1042 | { |
| 1043 | int l; |
| 1044 | int super; |
| 1045 | struct isl_tab_undo *snap, *snap2; |
| 1046 | unsigned n_eq = info[i].bmap->n_eq; |
| 1047 | |
| 1048 | for (l = 0; l < n; ++l) |
| 1049 | if (isl_tab_is_equality(info[i].tab, n_eq + relax[l])) |
| 1050 | return isl_change_none; |
| 1051 | |
| 1052 | snap = isl_tab_snap(info[i].tab); |
| 1053 | for (l = 0; l < n; ++l) |
| 1054 | if (isl_tab_relax(info[i].tab, n_eq + relax[l]) < 0) |
| 1055 | return isl_change_error; |
| 1056 | snap2 = isl_tab_snap(info[i].tab); |
| 1057 | for (l = 0; l < n; ++l) { |
| 1058 | if (isl_tab_rollback(info[i].tab, snap2) < 0) |
| 1059 | return isl_change_error; |
| 1060 | if (isl_tab_select_facet(info[i].tab, n_eq + relax[l]) < 0) |
| 1061 | return isl_change_error; |
| 1062 | if (tighten_on_relaxed_facet(&info[i], n, relax, l) < 0) |
| 1063 | return isl_change_error; |
| 1064 | super = contains(&info[j], info[i].tab); |
| 1065 | if (super < 0) |
| 1066 | return isl_change_error; |
| 1067 | if (super) |
| 1068 | continue; |
| 1069 | if (isl_tab_rollback(info[i].tab, snap) < 0) |
| 1070 | return isl_change_error; |
| 1071 | return isl_change_none; |
| 1072 | } |
| 1073 | |
| 1074 | if (isl_tab_rollback(info[i].tab, snap2) < 0) |
| 1075 | return isl_change_error; |
| 1076 | return extend(i, j, n, relax, info); |
| 1077 | } |
| 1078 | |
| 1079 | /* Data structure that keeps track of the wrapping constraints |
| 1080 | * and of information to bound the coefficients of those constraints. |
| 1081 | * |
| 1082 | * bound is set if we want to apply a bound on the coefficients |
| 1083 | * mat contains the wrapping constraints |
| 1084 | * max is the bound on the coefficients (if bound is set) |
| 1085 | */ |
| 1086 | struct isl_wraps { |
| 1087 | int bound; |
| 1088 | isl_mat *mat; |
| 1089 | isl_int max; |
| 1090 | }; |
| 1091 | |
| 1092 | /* Update wraps->max to be greater than or equal to the coefficients |
| 1093 | * in the equalities and inequalities of info->bmap that can be removed |
| 1094 | * if we end up applying wrapping. |
| 1095 | */ |
| 1096 | static void wraps_update_max(struct isl_wraps *wraps, |
| 1097 | struct isl_coalesce_info *info) |
| 1098 | { |
| 1099 | int k; |
| 1100 | isl_int max_k; |
| 1101 | unsigned total = isl_basic_map_total_dim(info->bmap); |
| 1102 | |
| 1103 | isl_int_init(max_k)isl_sioimath_init((max_k)); |
| 1104 | |
| 1105 | for (k = 0; k < info->bmap->n_eq; ++k) { |
| 1106 | if (info->eq[2 * k] == STATUS_VALID2 && |
| 1107 | info->eq[2 * k + 1] == STATUS_VALID2) |
| 1108 | continue; |
| 1109 | isl_seq_abs_max(info->bmap->eq[k] + 1, total, &max_k); |
| 1110 | if (isl_int_abs_gt(max_k, wraps->max)(isl_sioimath_abs_cmp(*(max_k), *(wraps->max)) > 0)) |
| 1111 | isl_int_set(wraps->max, max_k)isl_sioimath_set((wraps->max), *(max_k)); |
| 1112 | } |
| 1113 | |
| 1114 | for (k = 0; k < info->bmap->n_ineq; ++k) { |
| 1115 | if (info->ineq[k] == STATUS_VALID2 || |
| 1116 | info->ineq[k] == STATUS_REDUNDANT1) |
| 1117 | continue; |
| 1118 | isl_seq_abs_max(info->bmap->ineq[k] + 1, total, &max_k); |
| 1119 | if (isl_int_abs_gt(max_k, wraps->max)(isl_sioimath_abs_cmp(*(max_k), *(wraps->max)) > 0)) |
| 1120 | isl_int_set(wraps->max, max_k)isl_sioimath_set((wraps->max), *(max_k)); |
| 1121 | } |
| 1122 | |
| 1123 | isl_int_clear(max_k)isl_sioimath_clear((max_k)); |
| 1124 | } |
| 1125 | |
| 1126 | /* Initialize the isl_wraps data structure. |
| 1127 | * If we want to bound the coefficients of the wrapping constraints, |
| 1128 | * we set wraps->max to the largest coefficient |
| 1129 | * in the equalities and inequalities that can be removed if we end up |
| 1130 | * applying wrapping. |
| 1131 | */ |
| 1132 | static void wraps_init(struct isl_wraps *wraps, __isl_take isl_mat *mat, |
| 1133 | struct isl_coalesce_info *info, int i, int j) |
| 1134 | { |
| 1135 | isl_ctx *ctx; |
| 1136 | |
| 1137 | wraps->bound = 0; |
| 1138 | wraps->mat = mat; |
| 1139 | if (!mat) |
| 1140 | return; |
| 1141 | ctx = isl_mat_get_ctx(mat); |
| 1142 | wraps->bound = isl_options_get_coalesce_bounded_wrapping(ctx); |
| 1143 | if (!wraps->bound) |
| 1144 | return; |
| 1145 | isl_int_init(wraps->max)isl_sioimath_init((wraps->max)); |
| 1146 | isl_int_set_si(wraps->max, 0)isl_sioimath_set_si((wraps->max), 0); |
| 1147 | wraps_update_max(wraps, &info[i]); |
| 1148 | wraps_update_max(wraps, &info[j]); |
| 1149 | } |
| 1150 | |
| 1151 | /* Free the contents of the isl_wraps data structure. |
| 1152 | */ |
| 1153 | static void wraps_free(struct isl_wraps *wraps) |
| 1154 | { |
| 1155 | isl_mat_free(wraps->mat); |
| 1156 | if (wraps->bound) |
| 1157 | isl_int_clear(wraps->max)isl_sioimath_clear((wraps->max)); |
| 1158 | } |
| 1159 | |
| 1160 | /* Is the wrapping constraint in row "row" allowed? |
| 1161 | * |
| 1162 | * If wraps->bound is set, we check that none of the coefficients |
| 1163 | * is greater than wraps->max. |
| 1164 | */ |
| 1165 | static int allow_wrap(struct isl_wraps *wraps, int row) |
| 1166 | { |
| 1167 | int i; |
| 1168 | |
| 1169 | if (!wraps->bound) |
| 1170 | return 1; |
| 1171 | |
| 1172 | for (i = 1; i < wraps->mat->n_col; ++i) |
| 1173 | if (isl_int_abs_gt(wraps->mat->row[row][i], wraps->max)(isl_sioimath_abs_cmp(*(wraps->mat->row[row][i]), *(wraps ->max)) > 0)) |
| 1174 | return 0; |
| 1175 | |
| 1176 | return 1; |
| 1177 | } |
| 1178 | |
| 1179 | /* Wrap "ineq" (or its opposite if "negate" is set) around "bound" |
| 1180 | * to include "set" and add the result in position "w" of "wraps". |
| 1181 | * "len" is the total number of coefficients in "bound" and "ineq". |
| 1182 | * Return 1 on success, 0 on failure and -1 on error. |
| 1183 | * Wrapping can fail if the result of wrapping is equal to "bound" |
| 1184 | * or if we want to bound the sizes of the coefficients and |
| 1185 | * the wrapped constraint does not satisfy this bound. |
| 1186 | */ |
| 1187 | static int add_wrap(struct isl_wraps *wraps, int w, isl_int *bound, |
| 1188 | isl_int *ineq, unsigned len, __isl_keep isl_setisl_map *set, int negate) |
| 1189 | { |
| 1190 | isl_seq_cpy(wraps->mat->row[w], bound, len); |
| 1191 | if (negate) { |
| 1192 | isl_seq_neg(wraps->mat->row[w + 1], ineq, len); |
| 1193 | ineq = wraps->mat->row[w + 1]; |
| 1194 | } |
| 1195 | if (!isl_set_wrap_facet(set, wraps->mat->row[w], ineq)) |
| 1196 | return -1; |
| 1197 | if (isl_seq_eq(wraps->mat->row[w], bound, len)) |
| 1198 | return 0; |
| 1199 | if (!allow_wrap(wraps, w)) |
| 1200 | return 0; |
| 1201 | return 1; |
| 1202 | } |
| 1203 | |
| 1204 | /* For each constraint in info->bmap that is not redundant (as determined |
| 1205 | * by info->tab) and that is not a valid constraint for the other basic map, |
| 1206 | * wrap the constraint around "bound" such that it includes the whole |
| 1207 | * set "set" and append the resulting constraint to "wraps". |
| 1208 | * Note that the constraints that are valid for the other basic map |
| 1209 | * will be added to the combined basic map by default, so there is |
| 1210 | * no need to wrap them. |
| 1211 | * The caller wrap_in_facets even relies on this function not wrapping |
| 1212 | * any constraints that are already valid. |
| 1213 | * "wraps" is assumed to have been pre-allocated to the appropriate size. |
| 1214 | * wraps->n_row is the number of actual wrapped constraints that have |
| 1215 | * been added. |
| 1216 | * If any of the wrapping problems results in a constraint that is |
| 1217 | * identical to "bound", then this means that "set" is unbounded in such |
| 1218 | * way that no wrapping is possible. If this happens then wraps->n_row |
| 1219 | * is reset to zero. |
| 1220 | * Similarly, if we want to bound the coefficients of the wrapping |
| 1221 | * constraints and a newly added wrapping constraint does not |
| 1222 | * satisfy the bound, then wraps->n_row is also reset to zero. |
| 1223 | */ |
| 1224 | static int add_wraps(struct isl_wraps *wraps, struct isl_coalesce_info *info, |
| 1225 | isl_int *bound, __isl_keep isl_setisl_map *set) |
| 1226 | { |
| 1227 | int l, m; |
| 1228 | int w; |
| 1229 | int added; |
| 1230 | isl_basic_map *bmap = info->bmap; |
| 1231 | unsigned len = 1 + isl_basic_map_total_dim(bmap); |
| 1232 | |
| 1233 | w = wraps->mat->n_row; |
| 1234 | |
| 1235 | for (l = 0; l < bmap->n_ineq; ++l) { |
| 1236 | if (info->ineq[l] == STATUS_VALID2 || |
| 1237 | info->ineq[l] == STATUS_REDUNDANT1) |
| 1238 | continue; |
| 1239 | if (isl_seq_is_neg(bound, bmap->ineq[l], len)) |
| 1240 | continue; |
| 1241 | if (isl_seq_eq(bound, bmap->ineq[l], len)) |
| 1242 | continue; |
| 1243 | if (isl_tab_is_redundant(info->tab, bmap->n_eq + l)) |
| 1244 | continue; |
| 1245 | |
| 1246 | added = add_wrap(wraps, w, bound, bmap->ineq[l], len, set, 0); |
| 1247 | if (added < 0) |
| 1248 | return -1; |
| 1249 | if (!added) |
| 1250 | goto unbounded; |
| 1251 | ++w; |
| 1252 | } |
| 1253 | for (l = 0; l < bmap->n_eq; ++l) { |
| 1254 | if (isl_seq_is_neg(bound, bmap->eq[l], len)) |
| 1255 | continue; |
| 1256 | if (isl_seq_eq(bound, bmap->eq[l], len)) |
| 1257 | continue; |
| 1258 | |
| 1259 | for (m = 0; m < 2; ++m) { |
| 1260 | if (info->eq[2 * l + m] == STATUS_VALID2) |
| 1261 | continue; |
| 1262 | added = add_wrap(wraps, w, bound, bmap->eq[l], len, |
| 1263 | set, !m); |
| 1264 | if (added < 0) |
| 1265 | return -1; |
| 1266 | if (!added) |
| 1267 | goto unbounded; |
| 1268 | ++w; |
| 1269 | } |
| 1270 | } |
| 1271 | |
| 1272 | wraps->mat->n_row = w; |
| 1273 | return 0; |
| 1274 | unbounded: |
| 1275 | wraps->mat->n_row = 0; |
| 1276 | return 0; |
| 1277 | } |
| 1278 | |
| 1279 | /* Check if the constraints in "wraps" from "first" until the last |
| 1280 | * are all valid for the basic set represented by "tab". |
| 1281 | * If not, wraps->n_row is set to zero. |
| 1282 | */ |
| 1283 | static int check_wraps(__isl_keep isl_mat *wraps, int first, |
| 1284 | struct isl_tab *tab) |
| 1285 | { |
| 1286 | int i; |
| 1287 | |
| 1288 | for (i = first; i < wraps->n_row; ++i) { |
| 1289 | enum isl_ineq_type type; |
| 1290 | type = isl_tab_ineq_type(tab, wraps->row[i]); |
| 1291 | if (type == isl_ineq_error) |
| 1292 | return -1; |
| 1293 | if (type == isl_ineq_redundant) |
| 1294 | continue; |
| 1295 | wraps->n_row = 0; |
| 1296 | return 0; |
| 1297 | } |
| 1298 | |
| 1299 | return 0; |
| 1300 | } |
| 1301 | |
| 1302 | /* Return a set that corresponds to the non-redundant constraints |
| 1303 | * (as recorded in tab) of bmap. |
| 1304 | * |
| 1305 | * It's important to remove the redundant constraints as some |
| 1306 | * of the other constraints may have been modified after the |
| 1307 | * constraints were marked redundant. |
| 1308 | * In particular, a constraint may have been relaxed. |
| 1309 | * Redundant constraints are ignored when a constraint is relaxed |
| 1310 | * and should therefore continue to be ignored ever after. |
| 1311 | * Otherwise, the relaxation might be thwarted by some of |
| 1312 | * these constraints. |
| 1313 | * |
| 1314 | * Update the underlying set to ensure that the dimension doesn't change. |
| 1315 | * Otherwise the integer divisions could get dropped if the tab |
| 1316 | * turns out to be empty. |
| 1317 | */ |
| 1318 | static __isl_give isl_setisl_map *set_from_updated_bmap(__isl_keep isl_basic_map *bmap, |
| 1319 | struct isl_tab *tab) |
| 1320 | { |
| 1321 | isl_basic_setisl_basic_map *bset; |
| 1322 | |
| 1323 | bmap = isl_basic_map_copy(bmap); |
| 1324 | bset = isl_basic_map_underlying_set(bmap); |
| 1325 | bset = isl_basic_set_cow(bset); |
| 1326 | bset = isl_basic_set_update_from_tab(bset, tab); |
| 1327 | return isl_set_from_basic_set(bset); |
| 1328 | } |
| 1329 | |
| 1330 | /* Wrap the constraints of info->bmap that bound the facet defined |
| 1331 | * by inequality "k" around (the opposite of) this inequality to |
| 1332 | * include "set". "bound" may be used to store the negated inequality. |
| 1333 | * Since the wrapped constraints are not guaranteed to contain the whole |
| 1334 | * of info->bmap, we check them in check_wraps. |
| 1335 | * If any of the wrapped constraints turn out to be invalid, then |
| 1336 | * check_wraps will reset wrap->n_row to zero. |
| 1337 | */ |
| 1338 | static int add_wraps_around_facet(struct isl_wraps *wraps, |
| 1339 | struct isl_coalesce_info *info, int k, isl_int *bound, |
| 1340 | __isl_keep isl_setisl_map *set) |
| 1341 | { |
| 1342 | struct isl_tab_undo *snap; |
| 1343 | int n; |
| 1344 | unsigned total = isl_basic_map_total_dim(info->bmap); |
| 1345 | |
| 1346 | snap = isl_tab_snap(info->tab); |
| 1347 | |
| 1348 | if (isl_tab_select_facet(info->tab, info->bmap->n_eq + k) < 0) |
| 1349 | return -1; |
| 1350 | if (isl_tab_detect_redundant(info->tab) < 0) |
| 1351 | return -1; |
| 1352 | |
| 1353 | isl_seq_neg(bound, info->bmap->ineq[k], 1 + total); |
| 1354 | |
| 1355 | n = wraps->mat->n_row; |
| 1356 | if (add_wraps(wraps, info, bound, set) < 0) |
| 1357 | return -1; |
| 1358 | |
| 1359 | if (isl_tab_rollback(info->tab, snap) < 0) |
| 1360 | return -1; |
| 1361 | if (check_wraps(wraps->mat, n, info->tab) < 0) |
| 1362 | return -1; |
| 1363 | |
| 1364 | return 0; |
| 1365 | } |
| 1366 | |
| 1367 | /* Given a basic set i with a constraint k that is adjacent to |
| 1368 | * basic set j, check if we can wrap |
| 1369 | * both the facet corresponding to k (if "wrap_facet" is set) and basic map j |
| 1370 | * (always) around their ridges to include the other set. |
| 1371 | * If so, replace the pair of basic sets by their union. |
| 1372 | * |
| 1373 | * All constraints of i (except k) are assumed to be valid or |
| 1374 | * cut constraints for j. |
| 1375 | * Wrapping the cut constraints to include basic map j may result |
| 1376 | * in constraints that are no longer valid of basic map i |
| 1377 | * we have to check that the resulting wrapping constraints are valid for i. |
| 1378 | * If "wrap_facet" is not set, then all constraints of i (except k) |
| 1379 | * are assumed to be valid for j. |
| 1380 | * ____ _____ |
| 1381 | * / | / \ |
| 1382 | * / || / | |
| 1383 | * \ || => \ | |
| 1384 | * \ || \ | |
| 1385 | * \___|| \____| |
| 1386 | * |
| 1387 | */ |
| 1388 | static enum isl_change can_wrap_in_facet(int i, int j, int k, |
| 1389 | struct isl_coalesce_info *info, int wrap_facet) |
| 1390 | { |
| 1391 | enum isl_change change = isl_change_none; |
| 1392 | struct isl_wraps wraps; |
| 1393 | isl_ctx *ctx; |
| 1394 | isl_mat *mat; |
| 1395 | struct isl_setisl_map *set_i = NULL((void*)0); |
| 1396 | struct isl_setisl_map *set_j = NULL((void*)0); |
| 1397 | struct isl_vec *bound = NULL((void*)0); |
| 1398 | unsigned total = isl_basic_map_total_dim(info[i].bmap); |
| 1399 | |
| 1400 | set_i = set_from_updated_bmap(info[i].bmap, info[i].tab); |
| 1401 | set_j = set_from_updated_bmap(info[j].bmap, info[j].tab); |
| 1402 | ctx = isl_basic_map_get_ctx(info[i].bmap); |
| 1403 | mat = isl_mat_alloc(ctx, 2 * (info[i].bmap->n_eq + info[j].bmap->n_eq) + |
| 1404 | info[i].bmap->n_ineq + info[j].bmap->n_ineq, |
| 1405 | 1 + total); |
| 1406 | wraps_init(&wraps, mat, info, i, j); |
| 1407 | bound = isl_vec_alloc(ctx, 1 + total); |
| 1408 | if (!set_i || !set_j || !wraps.mat || !bound) |
| 1409 | goto error; |
| 1410 | |
| 1411 | isl_seq_cpy(bound->el, info[i].bmap->ineq[k], 1 + total); |
| 1412 | isl_int_add_ui(bound->el[0], bound->el[0], 1)isl_sioimath_add_ui((bound->el[0]), *(bound->el[0]), 1); |
| 1413 | |
| 1414 | isl_seq_cpy(wraps.mat->row[0], bound->el, 1 + total); |
| 1415 | wraps.mat->n_row = 1; |
| 1416 | |
| 1417 | if (add_wraps(&wraps, &info[j], bound->el, set_i) < 0) |
| 1418 | goto error; |
| 1419 | if (!wraps.mat->n_row) |
| 1420 | goto unbounded; |
| 1421 | |
| 1422 | if (wrap_facet) { |
| 1423 | if (add_wraps_around_facet(&wraps, &info[i], k, |
| 1424 | bound->el, set_j) < 0) |
| 1425 | goto error; |
| 1426 | if (!wraps.mat->n_row) |
| 1427 | goto unbounded; |
| 1428 | } |
| 1429 | |
| 1430 | change = fuse(i, j, info, wraps.mat, 0, 0); |
| 1431 | |
| 1432 | unbounded: |
| 1433 | wraps_free(&wraps); |
| 1434 | |
| 1435 | isl_set_free(set_i); |
| 1436 | isl_set_free(set_j); |
| 1437 | |
| 1438 | isl_vec_free(bound); |
| 1439 | |
| 1440 | return change; |
| 1441 | error: |
| 1442 | wraps_free(&wraps); |
| 1443 | isl_vec_free(bound); |
| 1444 | isl_set_free(set_i); |
| 1445 | isl_set_free(set_j); |
| 1446 | return isl_change_error; |
| 1447 | } |
| 1448 | |
| 1449 | /* Given a cut constraint t(x) >= 0 of basic map i, stored in row "w" |
| 1450 | * of wrap.mat, replace it by its relaxed version t(x) + 1 >= 0, and |
| 1451 | * add wrapping constraints to wrap.mat for all constraints |
| 1452 | * of basic map j that bound the part of basic map j that sticks out |
| 1453 | * of the cut constraint. |
| 1454 | * "set_i" is the underlying set of basic map i. |
| 1455 | * If any wrapping fails, then wraps->mat.n_row is reset to zero. |
| 1456 | * |
| 1457 | * In particular, we first intersect basic map j with t(x) + 1 = 0. |
| 1458 | * If the result is empty, then t(x) >= 0 was actually a valid constraint |
| 1459 | * (with respect to the integer points), so we add t(x) >= 0 instead. |
| 1460 | * Otherwise, we wrap the constraints of basic map j that are not |
| 1461 | * redundant in this intersection and that are not already valid |
| 1462 | * for basic map i over basic map i. |
| 1463 | * Note that it is sufficient to wrap the constraints to include |
| 1464 | * basic map i, because we will only wrap the constraints that do |
| 1465 | * not include basic map i already. The wrapped constraint will |
| 1466 | * therefore be more relaxed compared to the original constraint. |
| 1467 | * Since the original constraint is valid for basic map j, so is |
| 1468 | * the wrapped constraint. |
| 1469 | */ |
| 1470 | static isl_stat wrap_in_facet(struct isl_wraps *wraps, int w, |
| 1471 | struct isl_coalesce_info *info_j, __isl_keep isl_setisl_map *set_i, |
| 1472 | struct isl_tab_undo *snap) |
| 1473 | { |
| 1474 | isl_int_add_ui(wraps->mat->row[w][0], wraps->mat->row[w][0], 1)isl_sioimath_add_ui((wraps->mat->row[w][0]), *(wraps-> mat->row[w][0]), 1); |
| 1475 | if (isl_tab_add_eq(info_j->tab, wraps->mat->row[w]) < 0) |
| 1476 | return isl_stat_error; |
| 1477 | if (isl_tab_detect_redundant(info_j->tab) < 0) |
| 1478 | return isl_stat_error; |
| 1479 | |
| 1480 | if (info_j->tab->empty) |
| 1481 | isl_int_sub_ui(wraps->mat->row[w][0], wraps->mat->row[w][0], 1)isl_sioimath_sub_ui((wraps->mat->row[w][0]), *(wraps-> mat->row[w][0]), 1); |
| 1482 | else if (add_wraps(wraps, info_j, wraps->mat->row[w], set_i) < 0) |
| 1483 | return isl_stat_error; |
| 1484 | |
| 1485 | if (isl_tab_rollback(info_j->tab, snap) < 0) |
| 1486 | return isl_stat_error; |
| 1487 | |
| 1488 | return isl_stat_ok; |
| 1489 | } |
| 1490 | |
| 1491 | /* Given a pair of basic maps i and j such that j sticks out |
| 1492 | * of i at n cut constraints, each time by at most one, |
| 1493 | * try to compute wrapping constraints and replace the two |
| 1494 | * basic maps by a single basic map. |
| 1495 | * The other constraints of i are assumed to be valid for j. |
| 1496 | * "set_i" is the underlying set of basic map i. |
| 1497 | * "wraps" has been initialized to be of the right size. |
| 1498 | * |
| 1499 | * For each cut constraint t(x) >= 0 of i, we add the relaxed version |
| 1500 | * t(x) + 1 >= 0, along with wrapping constraints for all constraints |
| 1501 | * of basic map j that bound the part of basic map j that sticks out |
| 1502 | * of the cut constraint. |
| 1503 | * |
| 1504 | * If any wrapping fails, i.e., if we cannot wrap to touch |
| 1505 | * the union, then we give up. |
| 1506 | * Otherwise, the pair of basic maps is replaced by their union. |
| 1507 | */ |
| 1508 | static enum isl_change try_wrap_in_facets(int i, int j, |
| 1509 | struct isl_coalesce_info *info, struct isl_wraps *wraps, |
| 1510 | __isl_keep isl_setisl_map *set_i) |
| 1511 | { |
| 1512 | int k, l, w; |
| 1513 | unsigned total; |
| 1514 | struct isl_tab_undo *snap; |
| 1515 | |
| 1516 | total = isl_basic_map_total_dim(info[i].bmap); |
| 1517 | |
| 1518 | snap = isl_tab_snap(info[j].tab); |
| 1519 | |
| 1520 | wraps->mat->n_row = 0; |
| 1521 | |
| 1522 | for (k = 0; k < info[i].bmap->n_eq; ++k) { |
| 1523 | for (l = 0; l < 2; ++l) { |
| 1524 | if (info[i].eq[2 * k + l] != STATUS_CUT4) |
| 1525 | continue; |
| 1526 | w = wraps->mat->n_row++; |
| 1527 | if (l == 0) |
| 1528 | isl_seq_neg(wraps->mat->row[w], |
| 1529 | info[i].bmap->eq[k], 1 + total); |
| 1530 | else |
| 1531 | isl_seq_cpy(wraps->mat->row[w], |
| 1532 | info[i].bmap->eq[k], 1 + total); |
| 1533 | if (wrap_in_facet(wraps, w, &info[j], set_i, snap) < 0) |
| 1534 | return isl_change_error; |
| 1535 | |
| 1536 | if (!wraps->mat->n_row) |
| 1537 | return isl_change_none; |
| 1538 | } |
| 1539 | } |
| 1540 | |
| 1541 | for (k = 0; k < info[i].bmap->n_ineq; ++k) { |
| 1542 | if (info[i].ineq[k] != STATUS_CUT4) |
| 1543 | continue; |
| 1544 | w = wraps->mat->n_row++; |
| 1545 | isl_seq_cpy(wraps->mat->row[w], |
| 1546 | info[i].bmap->ineq[k], 1 + total); |
| 1547 | if (wrap_in_facet(wraps, w, &info[j], set_i, snap) < 0) |
| 1548 | return isl_change_error; |
| 1549 | |
| 1550 | if (!wraps->mat->n_row) |
| 1551 | return isl_change_none; |
| 1552 | } |
| 1553 | |
| 1554 | return fuse(i, j, info, wraps->mat, 0, 1); |
| 1555 | } |
| 1556 | |
| 1557 | /* Given a pair of basic maps i and j such that j sticks out |
| 1558 | * of i at n cut constraints, each time by at most one, |
| 1559 | * try to compute wrapping constraints and replace the two |
| 1560 | * basic maps by a single basic map. |
| 1561 | * The other constraints of i are assumed to be valid for j. |
| 1562 | * |
| 1563 | * The core computation is performed by try_wrap_in_facets. |
| 1564 | * This function simply extracts an underlying set representation |
| 1565 | * of basic map i and initializes the data structure for keeping |
| 1566 | * track of wrapping constraints. |
| 1567 | */ |
| 1568 | static enum isl_change wrap_in_facets(int i, int j, int n, |
| 1569 | struct isl_coalesce_info *info) |
| 1570 | { |
| 1571 | enum isl_change change = isl_change_none; |
| 1572 | struct isl_wraps wraps; |
| 1573 | isl_ctx *ctx; |
| 1574 | isl_mat *mat; |
| 1575 | isl_setisl_map *set_i = NULL((void*)0); |
| 1576 | unsigned total = isl_basic_map_total_dim(info[i].bmap); |
| 1577 | int max_wrap; |
| 1578 | |
| 1579 | if (isl_tab_extend_cons(info[j].tab, 1) < 0) |
| 1580 | return isl_change_error; |
| 1581 | |
| 1582 | max_wrap = 1 + 2 * info[j].bmap->n_eq + info[j].bmap->n_ineq; |
| 1583 | max_wrap *= n; |
| 1584 | |
| 1585 | set_i = set_from_updated_bmap(info[i].bmap, info[i].tab); |
| 1586 | ctx = isl_basic_map_get_ctx(info[i].bmap); |
| 1587 | mat = isl_mat_alloc(ctx, max_wrap, 1 + total); |
| 1588 | wraps_init(&wraps, mat, info, i, j); |
| 1589 | if (!set_i || !wraps.mat) |
| 1590 | goto error; |
| 1591 | |
| 1592 | change = try_wrap_in_facets(i, j, info, &wraps, set_i); |
| 1593 | |
| 1594 | wraps_free(&wraps); |
| 1595 | isl_set_free(set_i); |
| 1596 | |
| 1597 | return change; |
| 1598 | error: |
| 1599 | wraps_free(&wraps); |
| 1600 | isl_set_free(set_i); |
| 1601 | return isl_change_error; |
| 1602 | } |
| 1603 | |
| 1604 | /* Return the effect of inequality "ineq" on the tableau "tab", |
| 1605 | * after relaxing the constant term of "ineq" by one. |
| 1606 | */ |
| 1607 | static enum isl_ineq_type type_of_relaxed(struct isl_tab *tab, isl_int *ineq) |
| 1608 | { |
| 1609 | enum isl_ineq_type type; |
| 1610 | |
| 1611 | isl_int_add_ui(ineq[0], ineq[0], 1)isl_sioimath_add_ui((ineq[0]), *(ineq[0]), 1); |
| 1612 | type = isl_tab_ineq_type(tab, ineq); |
| 1613 | isl_int_sub_ui(ineq[0], ineq[0], 1)isl_sioimath_sub_ui((ineq[0]), *(ineq[0]), 1); |
| 1614 | |
| 1615 | return type; |
| 1616 | } |
| 1617 | |
| 1618 | /* Given two basic sets i and j, |
| 1619 | * check if relaxing all the cut constraints of i by one turns |
| 1620 | * them into valid constraint for j and check if we can wrap in |
| 1621 | * the bits that are sticking out. |
| 1622 | * If so, replace the pair by their union. |
| 1623 | * |
| 1624 | * We first check if all relaxed cut inequalities of i are valid for j |
| 1625 | * and then try to wrap in the intersections of the relaxed cut inequalities |
| 1626 | * with j. |
| 1627 | * |
| 1628 | * During this wrapping, we consider the points of j that lie at a distance |
| 1629 | * of exactly 1 from i. In particular, we ignore the points that lie in |
| 1630 | * between this lower-dimensional space and the basic map i. |
| 1631 | * We can therefore only apply this to integer maps. |
| 1632 | * ____ _____ |
| 1633 | * / ___|_ / \ |
| 1634 | * / | | / | |
| 1635 | * \ | | => \ | |
| 1636 | * \|____| \ | |
| 1637 | * \___| \____/ |
| 1638 | * |
| 1639 | * _____ ______ |
| 1640 | * | ____|_ | \ |
| 1641 | * | | | | | |
| 1642 | * | | | => | | |
| 1643 | * |_| | | | |
| 1644 | * |_____| \______| |
| 1645 | * |
| 1646 | * _______ |
| 1647 | * | | |
| 1648 | * | |\ | |
| 1649 | * | | \ | |
| 1650 | * | | \ | |
| 1651 | * | | \| |
| 1652 | * | | \ |
| 1653 | * | |_____\ |
| 1654 | * | | |
| 1655 | * |_______| |
| 1656 | * |
| 1657 | * Wrapping can fail if the result of wrapping one of the facets |
| 1658 | * around its edges does not produce any new facet constraint. |
| 1659 | * In particular, this happens when we try to wrap in unbounded sets. |
| 1660 | * |
| 1661 | * _______________________________________________________________________ |
| 1662 | * | |
| 1663 | * | ___ |
| 1664 | * | | | |
| 1665 | * |_| |_________________________________________________________________ |
| 1666 | * |___| |
| 1667 | * |
| 1668 | * The following is not an acceptable result of coalescing the above two |
| 1669 | * sets as it includes extra integer points. |
| 1670 | * _______________________________________________________________________ |
| 1671 | * | |
| 1672 | * | |
| 1673 | * | |
| 1674 | * | |
| 1675 | * \______________________________________________________________________ |
| 1676 | */ |
| 1677 | static enum isl_change can_wrap_in_set(int i, int j, |
| 1678 | struct isl_coalesce_info *info) |
| 1679 | { |
| 1680 | int k, l; |
| 1681 | int n; |
| 1682 | unsigned total; |
| 1683 | |
| 1684 | if (ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_RATIONAL)(!!(((info[i].bmap)->flags) & ((1 << 4)))) || |
| 1685 | ISL_F_ISSET(info[j].bmap, ISL_BASIC_MAP_RATIONAL)(!!(((info[j].bmap)->flags) & ((1 << 4))))) |
| 1686 | return isl_change_none; |
| 1687 | |
| 1688 | n = count(info[i].eq, 2 * info[i].bmap->n_eq, STATUS_CUT4); |
| 1689 | n += count(info[i].ineq, info[i].bmap->n_ineq, STATUS_CUT4); |
| 1690 | if (n == 0) |
| 1691 | return isl_change_none; |
| 1692 | |
| 1693 | total = isl_basic_map_total_dim(info[i].bmap); |
| 1694 | for (k = 0; k < info[i].bmap->n_eq; ++k) { |
| 1695 | for (l = 0; l < 2; ++l) { |
| 1696 | enum isl_ineq_type type; |
| 1697 | |
| 1698 | if (info[i].eq[2 * k + l] != STATUS_CUT4) |
| 1699 | continue; |
| 1700 | |
| 1701 | if (l == 0) |
| 1702 | isl_seq_neg(info[i].bmap->eq[k], |
| 1703 | info[i].bmap->eq[k], 1 + total); |
| 1704 | type = type_of_relaxed(info[j].tab, |
| 1705 | info[i].bmap->eq[k]); |
| 1706 | if (l == 0) |
| 1707 | isl_seq_neg(info[i].bmap->eq[k], |
| 1708 | info[i].bmap->eq[k], 1 + total); |
| 1709 | if (type == isl_ineq_error) |
| 1710 | return isl_change_error; |
| 1711 | if (type != isl_ineq_redundant) |
| 1712 | return isl_change_none; |
| 1713 | } |
| 1714 | } |
| 1715 | |
| 1716 | for (k = 0; k < info[i].bmap->n_ineq; ++k) { |
| 1717 | enum isl_ineq_type type; |
| 1718 | |
| 1719 | if (info[i].ineq[k] != STATUS_CUT4) |
| 1720 | continue; |
| 1721 | |
| 1722 | type = type_of_relaxed(info[j].tab, info[i].bmap->ineq[k]); |
| 1723 | if (type == isl_ineq_error) |
| 1724 | return isl_change_error; |
| 1725 | if (type != isl_ineq_redundant) |
| 1726 | return isl_change_none; |
| 1727 | } |
| 1728 | |
| 1729 | return wrap_in_facets(i, j, n, info); |
| 1730 | } |
| 1731 | |
| 1732 | /* Check if either i or j has only cut constraints that can |
| 1733 | * be used to wrap in (a facet of) the other basic set. |
| 1734 | * if so, replace the pair by their union. |
| 1735 | */ |
| 1736 | static enum isl_change check_wrap(int i, int j, struct isl_coalesce_info *info) |
| 1737 | { |
| 1738 | enum isl_change change = isl_change_none; |
| 1739 | |
| 1740 | change = can_wrap_in_set(i, j, info); |
| 1741 | if (change != isl_change_none) |
| 1742 | return change; |
| 1743 | |
| 1744 | change = can_wrap_in_set(j, i, info); |
| 1745 | return change; |
| 1746 | } |
| 1747 | |
| 1748 | /* Check if all inequality constraints of "i" that cut "j" cease |
| 1749 | * to be cut constraints if they are relaxed by one. |
| 1750 | * If so, collect the cut constraints in "list". |
| 1751 | * The caller is responsible for allocating "list". |
| 1752 | */ |
| 1753 | static isl_bool all_cut_by_one(int i, int j, struct isl_coalesce_info *info, |
| 1754 | int *list) |
| 1755 | { |
| 1756 | int l, n; |
| 1757 | |
| 1758 | n = 0; |
| 1759 | for (l = 0; l < info[i].bmap->n_ineq; ++l) { |
| 1760 | enum isl_ineq_type type; |
| 1761 | |
| 1762 | if (info[i].ineq[l] != STATUS_CUT4) |
| 1763 | continue; |
| 1764 | type = type_of_relaxed(info[j].tab, info[i].bmap->ineq[l]); |
| 1765 | if (type == isl_ineq_error) |
| 1766 | return isl_bool_error; |
| 1767 | if (type != isl_ineq_redundant) |
| 1768 | return isl_bool_false; |
| 1769 | list[n++] = l; |
| 1770 | } |
| 1771 | |
| 1772 | return isl_bool_true; |
| 1773 | } |
| 1774 | |
| 1775 | /* Given two basic maps such that "j" has at least one equality constraint |
| 1776 | * that is adjacent to an inequality constraint of "i" and such that "i" has |
| 1777 | * exactly one inequality constraint that is adjacent to an equality |
| 1778 | * constraint of "j", check whether "i" can be extended to include "j" or |
| 1779 | * whether "j" can be wrapped into "i". |
| 1780 | * All remaining constraints of "i" and "j" are assumed to be valid |
| 1781 | * or cut constraints of the other basic map. |
| 1782 | * However, none of the equality constraints of "i" are cut constraints. |
| 1783 | * |
| 1784 | * If "i" has any "cut" inequality constraints, then check if relaxing |
| 1785 | * each of them by one is sufficient for them to become valid. |
| 1786 | * If so, check if the inequality constraint adjacent to an equality |
| 1787 | * constraint of "j" along with all these cut constraints |
| 1788 | * can be relaxed by one to contain exactly "j". |
| 1789 | * Otherwise, or if this fails, check if "j" can be wrapped into "i". |
| 1790 | */ |
| 1791 | static enum isl_change check_single_adj_eq(int i, int j, |
| 1792 | struct isl_coalesce_info *info) |
| 1793 | { |
| 1794 | enum isl_change change = isl_change_none; |
| 1795 | int k; |
| 1796 | int n_cut; |
| 1797 | int *relax; |
| 1798 | isl_ctx *ctx; |
| 1799 | isl_bool try_relax; |
| 1800 | |
| 1801 | n_cut = count(info[i].ineq, info[i].bmap->n_ineq, STATUS_CUT4); |
| 1802 | |
| 1803 | k = find(info[i].ineq, info[i].bmap->n_ineq, STATUS_ADJ_EQ5); |
| 1804 | |
| 1805 | if (n_cut > 0) { |
| 1806 | ctx = isl_basic_map_get_ctx(info[i].bmap); |
| 1807 | relax = isl_calloc_array(ctx, int, 1 + n_cut)((int *)isl_calloc_or_die(ctx, 1 + n_cut, sizeof(int))); |
| 1808 | if (!relax) |
| 1809 | return isl_change_error; |
| 1810 | relax[0] = k; |
| 1811 | try_relax = all_cut_by_one(i, j, info, relax + 1); |
| 1812 | if (try_relax < 0) |
| 1813 | change = isl_change_error; |
| 1814 | } else { |
| 1815 | try_relax = isl_bool_true; |
| 1816 | relax = &k; |
| 1817 | } |
| 1818 | if (try_relax && change == isl_change_none) |
| 1819 | change = is_relaxed_extension(i, j, 1 + n_cut, relax, info); |
| 1820 | if (n_cut > 0) |
| 1821 | free(relax); |
| 1822 | if (change != isl_change_none) |
| 1823 | return change; |
| 1824 | |
| 1825 | change = can_wrap_in_facet(i, j, k, info, n_cut > 0); |
| 1826 | |
| 1827 | return change; |
| 1828 | } |
| 1829 | |
| 1830 | /* At least one of the basic maps has an equality that is adjacent |
| 1831 | * to inequality. Make sure that only one of the basic maps has |
| 1832 | * such an equality and that the other basic map has exactly one |
| 1833 | * inequality adjacent to an equality. |
| 1834 | * If the other basic map does not have such an inequality, then |
| 1835 | * check if all its constraints are either valid or cut constraints |
| 1836 | * and, if so, try wrapping in the first map into the second. |
| 1837 | * Otherwise, try to extend one basic map with the other or |
| 1838 | * wrap one basic map in the other. |
| 1839 | */ |
| 1840 | static enum isl_change check_adj_eq(int i, int j, |
| 1841 | struct isl_coalesce_info *info) |
| 1842 | { |
| 1843 | if (any(info[i].eq, 2 * info[i].bmap->n_eq, STATUS_ADJ_INEQ6) && |
| 1844 | any(info[j].eq, 2 * info[j].bmap->n_eq, STATUS_ADJ_INEQ6)) |
| 1845 | /* ADJ EQ TOO MANY */ |
| 1846 | return isl_change_none; |
| 1847 | |
| 1848 | if (any(info[i].eq, 2 * info[i].bmap->n_eq, STATUS_ADJ_INEQ6)) |
| 1849 | return check_adj_eq(j, i, info); |
| 1850 | |
| 1851 | /* j has an equality adjacent to an inequality in i */ |
| 1852 | |
| 1853 | if (count(info[i].ineq, info[i].bmap->n_ineq, STATUS_ADJ_EQ5) != 1) { |
| 1854 | if (all_valid_or_cut(&info[i])) |
| 1855 | return can_wrap_in_set(i, j, info); |
| 1856 | return isl_change_none; |
| 1857 | } |
| 1858 | if (any(info[i].eq, 2 * info[i].bmap->n_eq, STATUS_CUT4)) |
| 1859 | return isl_change_none; |
| 1860 | if (any(info[j].ineq, info[j].bmap->n_ineq, STATUS_ADJ_EQ5) || |
| 1861 | any(info[i].ineq, info[i].bmap->n_ineq, STATUS_ADJ_INEQ6) || |
| 1862 | any(info[j].ineq, info[j].bmap->n_ineq, STATUS_ADJ_INEQ6)) |
| 1863 | /* ADJ EQ TOO MANY */ |
| 1864 | return isl_change_none; |
| 1865 | |
| 1866 | return check_single_adj_eq(i, j, info); |
| 1867 | } |
| 1868 | |
| 1869 | /* The two basic maps lie on adjacent hyperplanes. In particular, |
| 1870 | * basic map "i" has an equality that lies parallel to basic map "j". |
| 1871 | * Check if we can wrap the facets around the parallel hyperplanes |
| 1872 | * to include the other set. |
| 1873 | * |
| 1874 | * We perform basically the same operations as can_wrap_in_facet, |
| 1875 | * except that we don't need to select a facet of one of the sets. |
| 1876 | * _ |
| 1877 | * \\ \\ |
| 1878 | * \\ => \\ |
| 1879 | * \ \| |
| 1880 | * |
| 1881 | * If there is more than one equality of "i" adjacent to an equality of "j", |
| 1882 | * then the result will satisfy one or more equalities that are a linear |
| 1883 | * combination of these equalities. These will be encoded as pairs |
| 1884 | * of inequalities in the wrapping constraints and need to be made |
| 1885 | * explicit. |
| 1886 | */ |
| 1887 | static enum isl_change check_eq_adj_eq(int i, int j, |
| 1888 | struct isl_coalesce_info *info) |
| 1889 | { |
| 1890 | int k; |
| 1891 | enum isl_change change = isl_change_none; |
| 1892 | int detect_equalities = 0; |
| 1893 | struct isl_wraps wraps; |
| 1894 | isl_ctx *ctx; |
| 1895 | isl_mat *mat; |
| 1896 | struct isl_setisl_map *set_i = NULL((void*)0); |
| 1897 | struct isl_setisl_map *set_j = NULL((void*)0); |
| 1898 | struct isl_vec *bound = NULL((void*)0); |
| 1899 | unsigned total = isl_basic_map_total_dim(info[i].bmap); |
| 1900 | |
| 1901 | if (count(info[i].eq, 2 * info[i].bmap->n_eq, STATUS_ADJ_EQ5) != 1) |
| 1902 | detect_equalities = 1; |
| 1903 | |
| 1904 | k = find(info[i].eq, 2 * info[i].bmap->n_eq, STATUS_ADJ_EQ5); |
| 1905 | |
| 1906 | set_i = set_from_updated_bmap(info[i].bmap, info[i].tab); |
| 1907 | set_j = set_from_updated_bmap(info[j].bmap, info[j].tab); |
| 1908 | ctx = isl_basic_map_get_ctx(info[i].bmap); |
| 1909 | mat = isl_mat_alloc(ctx, 2 * (info[i].bmap->n_eq + info[j].bmap->n_eq) + |
| 1910 | info[i].bmap->n_ineq + info[j].bmap->n_ineq, |
| 1911 | 1 + total); |
| 1912 | wraps_init(&wraps, mat, info, i, j); |
| 1913 | bound = isl_vec_alloc(ctx, 1 + total); |
| 1914 | if (!set_i || !set_j || !wraps.mat || !bound) |
| 1915 | goto error; |
| 1916 | |
| 1917 | if (k % 2 == 0) |
| 1918 | isl_seq_neg(bound->el, info[i].bmap->eq[k / 2], 1 + total); |
| 1919 | else |
| 1920 | isl_seq_cpy(bound->el, info[i].bmap->eq[k / 2], 1 + total); |
| 1921 | isl_int_add_ui(bound->el[0], bound->el[0], 1)isl_sioimath_add_ui((bound->el[0]), *(bound->el[0]), 1); |
| 1922 | |
| 1923 | isl_seq_cpy(wraps.mat->row[0], bound->el, 1 + total); |
| 1924 | wraps.mat->n_row = 1; |
| 1925 | |
| 1926 | if (add_wraps(&wraps, &info[j], bound->el, set_i) < 0) |
| 1927 | goto error; |
| 1928 | if (!wraps.mat->n_row) |
| 1929 | goto unbounded; |
| 1930 | |
| 1931 | isl_int_sub_ui(bound->el[0], bound->el[0], 1)isl_sioimath_sub_ui((bound->el[0]), *(bound->el[0]), 1); |
| 1932 | isl_seq_neg(bound->el, bound->el, 1 + total); |
| 1933 | |
| 1934 | isl_seq_cpy(wraps.mat->row[wraps.mat->n_row], bound->el, 1 + total); |
| 1935 | wraps.mat->n_row++; |
| 1936 | |
| 1937 | if (add_wraps(&wraps, &info[i], bound->el, set_j) < 0) |
| 1938 | goto error; |
| 1939 | if (!wraps.mat->n_row) |
| 1940 | goto unbounded; |
| 1941 | |
| 1942 | change = fuse(i, j, info, wraps.mat, detect_equalities, 0); |
| 1943 | |
| 1944 | if (0) { |
| 1945 | error: change = isl_change_error; |
| 1946 | } |
| 1947 | unbounded: |
| 1948 | |
| 1949 | wraps_free(&wraps); |
| 1950 | isl_set_free(set_i); |
| 1951 | isl_set_free(set_j); |
| 1952 | isl_vec_free(bound); |
| 1953 | |
| 1954 | return change; |
| 1955 | } |
| 1956 | |
| 1957 | /* Initialize the "eq" and "ineq" fields of "info". |
| 1958 | */ |
| 1959 | static void init_status(struct isl_coalesce_info *info) |
| 1960 | { |
| 1961 | info->eq = info->ineq = NULL((void*)0); |
| 1962 | } |
| 1963 | |
| 1964 | /* Set info->eq to the positions of the equalities of info->bmap |
| 1965 | * with respect to the basic map represented by "tab". |
| 1966 | * If info->eq has already been computed, then do not compute it again. |
| 1967 | */ |
| 1968 | static void set_eq_status_in(struct isl_coalesce_info *info, |
| 1969 | struct isl_tab *tab) |
| 1970 | { |
| 1971 | if (info->eq) |
| 1972 | return; |
| 1973 | info->eq = eq_status_in(info->bmap, tab); |
| 1974 | } |
| 1975 | |
| 1976 | /* Set info->ineq to the positions of the inequalities of info->bmap |
| 1977 | * with respect to the basic map represented by "tab". |
| 1978 | * If info->ineq has already been computed, then do not compute it again. |
| 1979 | */ |
| 1980 | static void set_ineq_status_in(struct isl_coalesce_info *info, |
| 1981 | struct isl_tab *tab) |
| 1982 | { |
| 1983 | if (info->ineq) |
| 1984 | return; |
| 1985 | info->ineq = ineq_status_in(info->bmap, info->tab, tab); |
| 1986 | } |
| 1987 | |
| 1988 | /* Free the memory allocated by the "eq" and "ineq" fields of "info". |
| 1989 | * This function assumes that init_status has been called on "info" first, |
| 1990 | * after which the "eq" and "ineq" fields may or may not have been |
| 1991 | * assigned a newly allocated array. |
| 1992 | */ |
| 1993 | static void clear_status(struct isl_coalesce_info *info) |
| 1994 | { |
| 1995 | free(info->eq); |
| 1996 | free(info->ineq); |
| 1997 | } |
| 1998 | |
| 1999 | /* Check if the union of the given pair of basic maps |
| 2000 | * can be represented by a single basic map. |
| 2001 | * If so, replace the pair by the single basic map and return |
| 2002 | * isl_change_drop_first, isl_change_drop_second or isl_change_fuse. |
| 2003 | * Otherwise, return isl_change_none. |
| 2004 | * The two basic maps are assumed to live in the same local space. |
| 2005 | * The "eq" and "ineq" fields of info[i] and info[j] are assumed |
| 2006 | * to have been initialized by the caller, either to NULL or |
| 2007 | * to valid information. |
| 2008 | * |
| 2009 | * We first check the effect of each constraint of one basic map |
| 2010 | * on the other basic map. |
| 2011 | * The constraint may be |
| 2012 | * redundant the constraint is redundant in its own |
| 2013 | * basic map and should be ignore and removed |
| 2014 | * in the end |
| 2015 | * valid all (integer) points of the other basic map |
| 2016 | * satisfy the constraint |
| 2017 | * separate no (integer) point of the other basic map |
| 2018 | * satisfies the constraint |
| 2019 | * cut some but not all points of the other basic map |
| 2020 | * satisfy the constraint |
| 2021 | * adj_eq the given constraint is adjacent (on the outside) |
| 2022 | * to an equality of the other basic map |
| 2023 | * adj_ineq the given constraint is adjacent (on the outside) |
| 2024 | * to an inequality of the other basic map |
| 2025 | * |
| 2026 | * We consider seven cases in which we can replace the pair by a single |
| 2027 | * basic map. We ignore all "redundant" constraints. |
| 2028 | * |
| 2029 | * 1. all constraints of one basic map are valid |
| 2030 | * => the other basic map is a subset and can be removed |
| 2031 | * |
| 2032 | * 2. all constraints of both basic maps are either "valid" or "cut" |
| 2033 | * and the facets corresponding to the "cut" constraints |
| 2034 | * of one of the basic maps lies entirely inside the other basic map |
| 2035 | * => the pair can be replaced by a basic map consisting |
| 2036 | * of the valid constraints in both basic maps |
| 2037 | * |
| 2038 | * 3. there is a single pair of adjacent inequalities |
| 2039 | * (all other constraints are "valid") |
| 2040 | * => the pair can be replaced by a basic map consisting |
| 2041 | * of the valid constraints in both basic maps |
| 2042 | * |
| 2043 | * 4. one basic map has a single adjacent inequality, while the other |
| 2044 | * constraints are "valid". The other basic map has some |
| 2045 | * "cut" constraints, but replacing the adjacent inequality by |
| 2046 | * its opposite and adding the valid constraints of the other |
| 2047 | * basic map results in a subset of the other basic map |
| 2048 | * => the pair can be replaced by a basic map consisting |
| 2049 | * of the valid constraints in both basic maps |
| 2050 | * |
| 2051 | * 5. there is a single adjacent pair of an inequality and an equality, |
| 2052 | * the other constraints of the basic map containing the inequality are |
| 2053 | * "valid". Moreover, if the inequality the basic map is relaxed |
| 2054 | * and then turned into an equality, then resulting facet lies |
| 2055 | * entirely inside the other basic map |
| 2056 | * => the pair can be replaced by the basic map containing |
| 2057 | * the inequality, with the inequality relaxed. |
| 2058 | * |
| 2059 | * 6. there is a single adjacent pair of an inequality and an equality, |
| 2060 | * the other constraints of the basic map containing the inequality are |
| 2061 | * "valid". Moreover, the facets corresponding to both |
| 2062 | * the inequality and the equality can be wrapped around their |
| 2063 | * ridges to include the other basic map |
| 2064 | * => the pair can be replaced by a basic map consisting |
| 2065 | * of the valid constraints in both basic maps together |
| 2066 | * with all wrapping constraints |
| 2067 | * |
| 2068 | * 7. one of the basic maps extends beyond the other by at most one. |
| 2069 | * Moreover, the facets corresponding to the cut constraints and |
| 2070 | * the pieces of the other basic map at offset one from these cut |
| 2071 | * constraints can be wrapped around their ridges to include |
| 2072 | * the union of the two basic maps |
| 2073 | * => the pair can be replaced by a basic map consisting |
| 2074 | * of the valid constraints in both basic maps together |
| 2075 | * with all wrapping constraints |
| 2076 | * |
| 2077 | * 8. the two basic maps live in adjacent hyperplanes. In principle |
| 2078 | * such sets can always be combined through wrapping, but we impose |
| 2079 | * that there is only one such pair, to avoid overeager coalescing. |
| 2080 | * |
| 2081 | * Throughout the computation, we maintain a collection of tableaus |
| 2082 | * corresponding to the basic maps. When the basic maps are dropped |
| 2083 | * or combined, the tableaus are modified accordingly. |
| 2084 | */ |
| 2085 | static enum isl_change coalesce_local_pair_reuse(int i, int j, |
| 2086 | struct isl_coalesce_info *info) |
| 2087 | { |
| 2088 | enum isl_change change = isl_change_none; |
| 2089 | |
| 2090 | set_eq_status_in(&info[i], info[j].tab); |
| 2091 | if (info[i].bmap->n_eq && !info[i].eq) |
| 2092 | goto error; |
| 2093 | if (any(info[i].eq, 2 * info[i].bmap->n_eq, STATUS_ERROR-1)) |
| 2094 | goto error; |
| 2095 | if (any(info[i].eq, 2 * info[i].bmap->n_eq, STATUS_SEPARATE3)) |
| 2096 | goto done; |
| 2097 | |
| 2098 | set_eq_status_in(&info[j], info[i].tab); |
| 2099 | if (info[j].bmap->n_eq && !info[j].eq) |
| 2100 | goto error; |
| 2101 | if (any(info[j].eq, 2 * info[j].bmap->n_eq, STATUS_ERROR-1)) |
| 2102 | goto error; |
| 2103 | if (any(info[j].eq, 2 * info[j].bmap->n_eq, STATUS_SEPARATE3)) |
| 2104 | goto done; |
| 2105 | |
| 2106 | set_ineq_status_in(&info[i], info[j].tab); |
| 2107 | if (info[i].bmap->n_ineq && !info[i].ineq) |
| 2108 | goto error; |
| 2109 | if (any(info[i].ineq, info[i].bmap->n_ineq, STATUS_ERROR-1)) |
| 2110 | goto error; |
| 2111 | if (any(info[i].ineq, info[i].bmap->n_ineq, STATUS_SEPARATE3)) |
| 2112 | goto done; |
| 2113 | |
| 2114 | set_ineq_status_in(&info[j], info[i].tab); |
| 2115 | if (info[j].bmap->n_ineq && !info[j].ineq) |
| 2116 | goto error; |
| 2117 | if (any(info[j].ineq, info[j].bmap->n_ineq, STATUS_ERROR-1)) |
| 2118 | goto error; |
| 2119 | if (any(info[j].ineq, info[j].bmap->n_ineq, STATUS_SEPARATE3)) |
| 2120 | goto done; |
| 2121 | |
| 2122 | if (all(info[i].eq, 2 * info[i].bmap->n_eq, STATUS_VALID2) && |
| 2123 | all(info[i].ineq, info[i].bmap->n_ineq, STATUS_VALID2)) { |
| 2124 | drop(&info[j]); |
| 2125 | change = isl_change_drop_second; |
| 2126 | } else if (all(info[j].eq, 2 * info[j].bmap->n_eq, STATUS_VALID2) && |
| 2127 | all(info[j].ineq, info[j].bmap->n_ineq, STATUS_VALID2)) { |
| 2128 | drop(&info[i]); |
| 2129 | change = isl_change_drop_first; |
| 2130 | } else if (any(info[i].eq, 2 * info[i].bmap->n_eq, STATUS_ADJ_EQ5)) { |
| 2131 | change = check_eq_adj_eq(i, j, info); |
| 2132 | } else if (any(info[j].eq, 2 * info[j].bmap->n_eq, STATUS_ADJ_EQ5)) { |
| 2133 | change = check_eq_adj_eq(j, i, info); |
| 2134 | } else if (any(info[i].eq, 2 * info[i].bmap->n_eq, STATUS_ADJ_INEQ6) || |
| 2135 | any(info[j].eq, 2 * info[j].bmap->n_eq, STATUS_ADJ_INEQ6)) { |
| 2136 | change = check_adj_eq(i, j, info); |
| 2137 | } else if (any(info[i].ineq, info[i].bmap->n_ineq, STATUS_ADJ_EQ5) || |
| 2138 | any(info[j].ineq, info[j].bmap->n_ineq, STATUS_ADJ_EQ5)) { |
| 2139 | /* Can't happen */ |
| 2140 | /* BAD ADJ INEQ */ |
| 2141 | } else if (any(info[i].ineq, info[i].bmap->n_ineq, STATUS_ADJ_INEQ6) || |
| 2142 | any(info[j].ineq, info[j].bmap->n_ineq, STATUS_ADJ_INEQ6)) { |
| 2143 | change = check_adj_ineq(i, j, info); |
| 2144 | } else { |
| 2145 | if (!any(info[i].eq, 2 * info[i].bmap->n_eq, STATUS_CUT4) && |
| 2146 | !any(info[j].eq, 2 * info[j].bmap->n_eq, STATUS_CUT4)) |
| 2147 | change = check_facets(i, j, info); |
| 2148 | if (change == isl_change_none) |
| 2149 | change = check_wrap(i, j, info); |
| 2150 | } |
| 2151 | |
| 2152 | done: |
| 2153 | clear_status(&info[i]); |
| 2154 | clear_status(&info[j]); |
| 2155 | return change; |
| 2156 | error: |
| 2157 | clear_status(&info[i]); |
| 2158 | clear_status(&info[j]); |
| 2159 | return isl_change_error; |
| 2160 | } |
| 2161 | |
| 2162 | /* Check if the union of the given pair of basic maps |
| 2163 | * can be represented by a single basic map. |
| 2164 | * If so, replace the pair by the single basic map and return |
| 2165 | * isl_change_drop_first, isl_change_drop_second or isl_change_fuse. |
| 2166 | * Otherwise, return isl_change_none. |
| 2167 | * The two basic maps are assumed to live in the same local space. |
| 2168 | */ |
| 2169 | static enum isl_change coalesce_local_pair(int i, int j, |
| 2170 | struct isl_coalesce_info *info) |
| 2171 | { |
| 2172 | init_status(&info[i]); |
| 2173 | init_status(&info[j]); |
| 2174 | return coalesce_local_pair_reuse(i, j, info); |
| 2175 | } |
| 2176 | |
| 2177 | /* Shift the integer division at position "div" of the basic map |
| 2178 | * represented by "info" by "shift". |
| 2179 | * |
| 2180 | * That is, if the integer division has the form |
| 2181 | * |
| 2182 | * floor(f(x)/d) |
| 2183 | * |
| 2184 | * then replace it by |
| 2185 | * |
| 2186 | * floor((f(x) + shift * d)/d) - shift |
| 2187 | */ |
| 2188 | static isl_stat shift_div(struct isl_coalesce_info *info, int div, |
| 2189 | isl_int shift) |
| 2190 | { |
| 2191 | unsigned total; |
| 2192 | |
| 2193 | info->bmap = isl_basic_map_shift_div(info->bmap, div, 0, shift); |
| 2194 | if (!info->bmap) |
| 2195 | return isl_stat_error; |
| 2196 | |
| 2197 | total = isl_basic_map_dim(info->bmap, isl_dim_all); |
| 2198 | total -= isl_basic_map_dim(info->bmap, isl_dim_div); |
| 2199 | if (isl_tab_shift_var(info->tab, total + div, shift) < 0) |
| 2200 | return isl_stat_error; |
| 2201 | |
| 2202 | return isl_stat_ok; |
| 2203 | } |
| 2204 | |
| 2205 | /* If the integer division at position "div" is defined by an equality, |
| 2206 | * i.e., a stride constraint, then change the integer division expression |
| 2207 | * to have a constant term equal to zero. |
| 2208 | * |
| 2209 | * Let the equality constraint be |
| 2210 | * |
| 2211 | * c + f + m a = 0 |
| 2212 | * |
| 2213 | * The integer division expression is then of the form |
| 2214 | * |
| 2215 | * a = floor((-f - c')/m) |
| 2216 | * |
| 2217 | * The integer division is first shifted by t = floor(c/m), |
| 2218 | * turning the equality constraint into |
| 2219 | * |
| 2220 | * c - m floor(c/m) + f + m a' = 0 |
| 2221 | * |
| 2222 | * i.e., |
| 2223 | * |
| 2224 | * (c mod m) + f + m a' = 0 |
| 2225 | * |
| 2226 | * That is, |
| 2227 | * |
| 2228 | * a' = (-f - (c mod m))/m = floor((-f)/m) |
| 2229 | * |
| 2230 | * because a' is an integer and 0 <= (c mod m) < m. |
| 2231 | * The constant term of a' can therefore be zeroed out. |
| 2232 | */ |
| 2233 | static isl_stat normalize_stride_div(struct isl_coalesce_info *info, int div) |
| 2234 | { |
| 2235 | isl_bool defined; |
| 2236 | isl_stat r; |
| 2237 | isl_constraint *c; |
| 2238 | isl_int shift, stride; |
| 2239 | |
| 2240 | defined = isl_basic_map_has_defining_equality(info->bmap, isl_dim_div, |
| 2241 | div, &c); |
| 2242 | if (defined < 0) |
| 2243 | return isl_stat_error; |
| 2244 | if (!defined) |
| 2245 | return isl_stat_ok; |
| 2246 | if (!c) |
| 2247 | return isl_stat_error; |
| 2248 | isl_int_init(shift)isl_sioimath_init((shift)); |
| 2249 | isl_int_init(stride)isl_sioimath_init((stride)); |
| 2250 | isl_constraint_get_constant(c, &shift); |
| 2251 | isl_constraint_get_coefficient(c, isl_dim_div, div, &stride); |
| 2252 | isl_int_fdiv_q(shift, shift, stride)isl_sioimath_fdiv_q((shift), *(shift), *(stride)); |
| 2253 | r = shift_div(info, div, shift); |
| 2254 | isl_int_clear(stride)isl_sioimath_clear((stride)); |
| 2255 | isl_int_clear(shift)isl_sioimath_clear((shift)); |
| 2256 | isl_constraint_free(c); |
| 2257 | if (r < 0) |
| 2258 | return isl_stat_error; |
| 2259 | info->bmap = isl_basic_map_set_div_expr_constant_num_si_inplace( |
| 2260 | info->bmap, div, 0); |
| 2261 | if (!info->bmap) |
| 2262 | return isl_stat_error; |
| 2263 | return isl_stat_ok; |
| 2264 | } |
| 2265 | |
| 2266 | /* The basic maps represented by "info1" and "info2" are known |
| 2267 | * to have the same number of integer divisions. |
| 2268 | * Check if pairs of integer divisions are equal to each other |
| 2269 | * despite the fact that they differ by a rational constant. |
| 2270 | * |
| 2271 | * In particular, look for any pair of integer divisions that |
| 2272 | * only differ in their constant terms. |
| 2273 | * If either of these integer divisions is defined |
| 2274 | * by stride constraints, then modify it to have a zero constant term. |
| 2275 | * If both are defined by stride constraints then in the end they will have |
| 2276 | * the same (zero) constant term. |
| 2277 | */ |
| 2278 | static isl_stat harmonize_stride_divs(struct isl_coalesce_info *info1, |
| 2279 | struct isl_coalesce_info *info2) |
| 2280 | { |
| 2281 | int i, n; |
| 2282 | int total; |
| 2283 | |
| 2284 | total = isl_basic_map_total_dim(info1->bmap); |
Value stored to 'total' is never read | |
| 2285 | n = isl_basic_map_dim(info1->bmap, isl_dim_div); |
| 2286 | for (i = 0; i < n; ++i) { |
| 2287 | isl_bool known, harmonize; |
| 2288 | |
| 2289 | known = isl_basic_map_div_is_known(info1->bmap, i); |
| 2290 | if (known >= 0 && known) |
| 2291 | known = isl_basic_map_div_is_known(info2->bmap, i); |
| 2292 | if (known < 0) |
| 2293 | return isl_stat_error; |
| 2294 | if (!known) |
| 2295 | continue; |
| 2296 | harmonize = isl_basic_map_equal_div_expr_except_constant( |
| 2297 | info1->bmap, i, info2->bmap, i); |
| 2298 | if (harmonize < 0) |
| 2299 | return isl_stat_error; |
| 2300 | if (!harmonize) |
| 2301 | continue; |
| 2302 | if (normalize_stride_div(info1, i) < 0) |
| 2303 | return isl_stat_error; |
| 2304 | if (normalize_stride_div(info2, i) < 0) |
| 2305 | return isl_stat_error; |
| 2306 | } |
| 2307 | |
| 2308 | return isl_stat_ok; |
| 2309 | } |
| 2310 | |
| 2311 | /* If "shift" is an integer constant, then shift the integer division |
| 2312 | * at position "div" of the basic map represented by "info" by "shift". |
| 2313 | * If "shift" is not an integer constant, then do nothing. |
| 2314 | * If "shift" is equal to zero, then no shift needs to be performed either. |
| 2315 | * |
| 2316 | * That is, if the integer division has the form |
| 2317 | * |
| 2318 | * floor(f(x)/d) |
| 2319 | * |
| 2320 | * then replace it by |
| 2321 | * |
| 2322 | * floor((f(x) + shift * d)/d) - shift |
| 2323 | */ |
| 2324 | static isl_stat shift_if_cst_int(struct isl_coalesce_info *info, int div, |
| 2325 | __isl_keep isl_aff *shift) |
| 2326 | { |
| 2327 | isl_bool cst; |
| 2328 | isl_stat r; |
| 2329 | isl_int d; |
| 2330 | isl_val *c; |
| 2331 | |
| 2332 | cst = isl_aff_is_cst(shift); |
| 2333 | if (cst < 0 || !cst) |
| 2334 | return cst < 0 ? isl_stat_error : isl_stat_ok; |
| 2335 | |
| 2336 | c = isl_aff_get_constant_val(shift); |
| 2337 | cst = isl_val_is_int(c); |
| 2338 | if (cst >= 0 && cst) |
| 2339 | cst = isl_bool_not(isl_val_is_zero(c)); |
| 2340 | if (cst < 0 || !cst) { |
| 2341 | isl_val_free(c); |
| 2342 | return cst < 0 ? isl_stat_error : isl_stat_ok; |
| 2343 | } |
| 2344 | |
| 2345 | isl_int_init(d)isl_sioimath_init((d)); |
| 2346 | r = isl_val_get_num_isl_int(c, &d); |
| 2347 | if (r >= 0) |
| 2348 | r = shift_div(info, div, d); |
| 2349 | isl_int_clear(d)isl_sioimath_clear((d)); |
| 2350 | |
| 2351 | isl_val_free(c); |
| 2352 | |
| 2353 | return r; |
| 2354 | } |
| 2355 | |
| 2356 | /* Check if some of the divs in the basic map represented by "info1" |
| 2357 | * are shifts of the corresponding divs in the basic map represented |
| 2358 | * by "info2", taking into account the equality constraints "eq1" of "info1" |
| 2359 | * and "eq2" of "info2". If so, align them with those of "info2". |
| 2360 | * "info1" and "info2" are assumed to have the same number |
| 2361 | * of integer divisions. |
| 2362 | * |
| 2363 | * An integer division is considered to be a shift of another integer |
| 2364 | * division if, after simplification with respect to the equality |
| 2365 | * constraints of the other basic map, one is equal to the other |
| 2366 | * plus a constant. |
| 2367 | * |
| 2368 | * In particular, for each pair of integer divisions, if both are known, |
| 2369 | * have the same denominator and are not already equal to each other, |
| 2370 | * simplify each with respect to the equality constraints |
| 2371 | * of the other basic map. If the difference is an integer constant, |
| 2372 | * then move this difference outside. |
| 2373 | * That is, if, after simplification, one integer division is of the form |
| 2374 | * |
| 2375 | * floor((f(x) + c_1)/d) |
| 2376 | * |
| 2377 | * while the other is of the form |
| 2378 | * |
| 2379 | * floor((f(x) + c_2)/d) |
| 2380 | * |
| 2381 | * and n = (c_2 - c_1)/d is an integer, then replace the first |
| 2382 | * integer division by |
| 2383 | * |
| 2384 | * floor((f_1(x) + c_1 + n * d)/d) - n, |
| 2385 | * |
| 2386 | * where floor((f_1(x) + c_1 + n * d)/d) = floor((f2(x) + c_2)/d) |
| 2387 | * after simplification with respect to the equality constraints. |
| 2388 | */ |
| 2389 | static isl_stat harmonize_divs_with_hulls(struct isl_coalesce_info *info1, |
| 2390 | struct isl_coalesce_info *info2, __isl_keep isl_basic_setisl_basic_map *eq1, |
| 2391 | __isl_keep isl_basic_setisl_basic_map *eq2) |
| 2392 | { |
| 2393 | int i; |
| 2394 | int total; |
| 2395 | isl_local_space *ls1, *ls2; |
| 2396 | |
| 2397 | total = isl_basic_map_total_dim(info1->bmap); |
| 2398 | ls1 = isl_local_space_wrap(isl_basic_map_get_local_space(info1->bmap)); |
| 2399 | ls2 = isl_local_space_wrap(isl_basic_map_get_local_space(info2->bmap)); |
| 2400 | for (i = 0; i < info1->bmap->n_div; ++i) { |
| 2401 | isl_stat r; |
| 2402 | isl_aff *div1, *div2; |
| 2403 | |
| 2404 | if (!isl_local_space_div_is_known(ls1, i) || |
| 2405 | !isl_local_space_div_is_known(ls2, i)) |
| 2406 | continue; |
| 2407 | if (isl_int_ne(info1->bmap->div[i][0], info2->bmap->div[i][0])(isl_sioimath_cmp(*(info1->bmap->div[i][0]), *(info2-> bmap->div[i][0])) != 0)) |
| 2408 | continue; |
| 2409 | if (isl_seq_eq(info1->bmap->div[i] + 1, |
| 2410 | info2->bmap->div[i] + 1, 1 + total)) |
| 2411 | continue; |
| 2412 | div1 = isl_local_space_get_div(ls1, i); |
| 2413 | div2 = isl_local_space_get_div(ls2, i); |
| 2414 | div1 = isl_aff_substitute_equalities(div1, |
| 2415 | isl_basic_set_copy(eq2)); |
| 2416 | div2 = isl_aff_substitute_equalities(div2, |
| 2417 | isl_basic_set_copy(eq1)); |
| 2418 | div2 = isl_aff_sub(div2, div1); |
| 2419 | r = shift_if_cst_int(info1, i, div2); |
| 2420 | isl_aff_free(div2); |
| 2421 | if (r < 0) |
| 2422 | break; |
| 2423 | } |
| 2424 | isl_local_space_free(ls1); |
| 2425 | isl_local_space_free(ls2); |
| 2426 | |
| 2427 | if (i < info1->bmap->n_div) |
| 2428 | return isl_stat_error; |
| 2429 | return isl_stat_ok; |
| 2430 | } |
| 2431 | |
| 2432 | /* Check if some of the divs in the basic map represented by "info1" |
| 2433 | * are shifts of the corresponding divs in the basic map represented |
| 2434 | * by "info2". If so, align them with those of "info2". |
| 2435 | * Only do this if "info1" and "info2" have the same number |
| 2436 | * of integer divisions. |
| 2437 | * |
| 2438 | * An integer division is considered to be a shift of another integer |
| 2439 | * division if, after simplification with respect to the equality |
| 2440 | * constraints of the other basic map, one is equal to the other |
| 2441 | * plus a constant. |
| 2442 | * |
| 2443 | * First check if pairs of integer divisions are equal to each other |
| 2444 | * despite the fact that they differ by a rational constant. |
| 2445 | * If so, try and arrange for them to have the same constant term. |
| 2446 | * |
| 2447 | * Then, extract the equality constraints and continue with |
| 2448 | * harmonize_divs_with_hulls. |
| 2449 | */ |
| 2450 | static isl_stat harmonize_divs(struct isl_coalesce_info *info1, |
| 2451 | struct isl_coalesce_info *info2) |
| 2452 | { |
| 2453 | isl_basic_map *bmap1, *bmap2; |
| 2454 | isl_basic_setisl_basic_map *eq1, *eq2; |
| 2455 | isl_stat r; |
| 2456 | |
| 2457 | if (!info1->bmap || !info2->bmap) |
| 2458 | return isl_stat_error; |
| 2459 | |
| 2460 | if (info1->bmap->n_div != info2->bmap->n_div) |
| 2461 | return isl_stat_ok; |
| 2462 | if (info1->bmap->n_div == 0) |
| 2463 | return isl_stat_ok; |
| 2464 | |
| 2465 | if (harmonize_stride_divs(info1, info2) < 0) |
| 2466 | return isl_stat_error; |
| 2467 | |
| 2468 | bmap1 = isl_basic_map_copy(info1->bmap); |
| 2469 | bmap2 = isl_basic_map_copy(info2->bmap); |
| 2470 | eq1 = isl_basic_map_wrap(isl_basic_map_plain_affine_hull(bmap1)); |
| 2471 | eq2 = isl_basic_map_wrap(isl_basic_map_plain_affine_hull(bmap2)); |
| 2472 | r = harmonize_divs_with_hulls(info1, info2, eq1, eq2); |
| 2473 | isl_basic_set_free(eq1); |
| 2474 | isl_basic_set_free(eq2); |
| 2475 | |
| 2476 | return r; |
| 2477 | } |
| 2478 | |
| 2479 | /* Do the two basic maps live in the same local space, i.e., |
| 2480 | * do they have the same (known) divs? |
| 2481 | * If either basic map has any unknown divs, then we can only assume |
| 2482 | * that they do not live in the same local space. |
| 2483 | */ |
| 2484 | static int same_divs(__isl_keep isl_basic_map *bmap1, |
| 2485 | __isl_keep isl_basic_map *bmap2) |
| 2486 | { |
| 2487 | int i; |
| 2488 | int known; |
| 2489 | int total; |
| 2490 | |
| 2491 | if (!bmap1 || !bmap2) |
| 2492 | return -1; |
| 2493 | if (bmap1->n_div != bmap2->n_div) |
| 2494 | return 0; |
| 2495 | |
| 2496 | if (bmap1->n_div == 0) |
| 2497 | return 1; |
| 2498 | |
| 2499 | known = isl_basic_map_divs_known(bmap1); |
| 2500 | if (known < 0 || !known) |
| 2501 | return known; |
| 2502 | known = isl_basic_map_divs_known(bmap2); |
| 2503 | if (known < 0 || !known) |
| 2504 | return known; |
| 2505 | |
| 2506 | total = isl_basic_map_total_dim(bmap1); |
| 2507 | for (i = 0; i < bmap1->n_div; ++i) |
| 2508 | if (!isl_seq_eq(bmap1->div[i], bmap2->div[i], 2 + total)) |
| 2509 | return 0; |
| 2510 | |
| 2511 | return 1; |
| 2512 | } |
| 2513 | |
| 2514 | /* Assuming that "tab" contains the equality constraints and |
| 2515 | * the initial inequality constraints of "bmap", copy the remaining |
| 2516 | * inequality constraints of "bmap" to "Tab". |
| 2517 | */ |
| 2518 | static isl_stat copy_ineq(struct isl_tab *tab, __isl_keep isl_basic_map *bmap) |
| 2519 | { |
| 2520 | int i, n_ineq; |
| 2521 | |
| 2522 | if (!bmap) |
| 2523 | return isl_stat_error; |
| 2524 | |
| 2525 | n_ineq = tab->n_con - tab->n_eq; |
| 2526 | for (i = n_ineq; i < bmap->n_ineq; ++i) |
| 2527 | if (isl_tab_add_ineq(tab, bmap->ineq[i]) < 0) |
| 2528 | return isl_stat_error; |
| 2529 | |
| 2530 | return isl_stat_ok; |
| 2531 | } |
| 2532 | |
| 2533 | /* Description of an integer division that is added |
| 2534 | * during an expansion. |
| 2535 | * "pos" is the position of the corresponding variable. |
| 2536 | * "cst" indicates whether this integer division has a fixed value. |
| 2537 | * "val" contains the fixed value, if the value is fixed. |
| 2538 | */ |
| 2539 | struct isl_expanded { |
| 2540 | int pos; |
| 2541 | isl_bool cst; |
| 2542 | isl_int val; |
| 2543 | }; |
| 2544 | |
| 2545 | /* For each of the "n" integer division variables "expanded", |
| 2546 | * if the variable has a fixed value, then add two inequality |
| 2547 | * constraints expressing the fixed value. |
| 2548 | * Otherwise, add the corresponding div constraints. |
| 2549 | * The caller is responsible for removing the div constraints |
| 2550 | * that it added for all these "n" integer divisions. |
| 2551 | * |
| 2552 | * The div constraints and the pair of inequality constraints |
| 2553 | * forcing the fixed value cannot both be added for a given variable |
| 2554 | * as the combination may render some of the original constraints redundant. |
| 2555 | * These would then be ignored during the coalescing detection, |
| 2556 | * while they could remain in the fused result. |
| 2557 | * |
| 2558 | * The two added inequality constraints are |
| 2559 | * |
| 2560 | * -a + v >= 0 |
| 2561 | * a - v >= 0 |
| 2562 | * |
| 2563 | * with "a" the variable and "v" its fixed value. |
| 2564 | * The facet corresponding to one of these two constraints is selected |
| 2565 | * in the tableau to ensure that the pair of inequality constraints |
| 2566 | * is treated as an equality constraint. |
| 2567 | * |
| 2568 | * The information in info->ineq is thrown away because it was |
| 2569 | * computed in terms of div constraints, while some of those |
| 2570 | * have now been replaced by these pairs of inequality constraints. |
| 2571 | */ |
| 2572 | static isl_stat fix_constant_divs(struct isl_coalesce_info *info, |
| 2573 | int n, struct isl_expanded *expanded) |
| 2574 | { |
| 2575 | unsigned o_div; |
| 2576 | int i; |
| 2577 | isl_vec *ineq; |
| 2578 | |
| 2579 | o_div = isl_basic_map_offset(info->bmap, isl_dim_div) - 1; |
| 2580 | ineq = isl_vec_alloc(isl_tab_get_ctx(info->tab), 1 + info->tab->n_var); |
| 2581 | if (!ineq) |
| 2582 | return isl_stat_error; |
| 2583 | isl_seq_clr(ineq->el + 1, info->tab->n_var); |
| 2584 | |
| 2585 | for (i = 0; i < n; ++i) { |
| 2586 | if (!expanded[i].cst) { |
| 2587 | info->bmap = isl_basic_map_extend_constraints( |
| 2588 | info->bmap, 0, 2); |
| 2589 | if (isl_basic_map_add_div_constraints(info->bmap, |
| 2590 | expanded[i].pos - o_div) < 0) |
| 2591 | break; |
| 2592 | } else { |
| 2593 | isl_int_set_si(ineq->el[1 + expanded[i].pos], -1)isl_sioimath_set_si((ineq->el[1 + expanded[i].pos]), -1); |
| 2594 | isl_int_set(ineq->el[0], expanded[i].val)isl_sioimath_set((ineq->el[0]), *(expanded[i].val)); |
| 2595 | info->bmap = isl_basic_map_add_ineq(info->bmap, |
| 2596 | ineq->el); |
| 2597 | isl_int_set_si(ineq->el[1 + expanded[i].pos], 1)isl_sioimath_set_si((ineq->el[1 + expanded[i].pos]), 1); |
| 2598 | isl_int_neg(ineq->el[0], expanded[i].val)isl_sioimath_neg((ineq->el[0]), *(expanded[i].val)); |
| 2599 | info->bmap = isl_basic_map_add_ineq(info->bmap, |
| 2600 | ineq->el); |
| 2601 | isl_int_set_si(ineq->el[1 + expanded[i].pos], 0)isl_sioimath_set_si((ineq->el[1 + expanded[i].pos]), 0); |
| 2602 | } |
| 2603 | if (copy_ineq(info->tab, info->bmap) < 0) |
| 2604 | break; |
| 2605 | if (expanded[i].cst && |
| 2606 | isl_tab_select_facet(info->tab, info->tab->n_con - 1) < 0) |
| 2607 | break; |
| 2608 | } |
| 2609 | |
| 2610 | isl_vec_free(ineq); |
| 2611 | |
| 2612 | clear_status(info); |
| 2613 | init_status(info); |
| 2614 | |
| 2615 | return i < n ? isl_stat_error : isl_stat_ok; |
| 2616 | } |
| 2617 | |
| 2618 | /* Insert the "n" integer division variables "expanded" |
| 2619 | * into info->tab and info->bmap and |
| 2620 | * update info->ineq with respect to the redundant constraints |
| 2621 | * in the resulting tableau. |
| 2622 | * "bmap" contains the result of this insertion in info->bmap, |
| 2623 | * while info->bmap is the original version |
| 2624 | * of "bmap", i.e., the one that corresponds to the current |
| 2625 | * state of info->tab. The number of constraints in info->bmap |
| 2626 | * is assumed to be the same as the number of constraints |
| 2627 | * in info->tab. This is required to be able to detect |
| 2628 | * the extra constraints in "bmap". |
| 2629 | * |
| 2630 | * In particular, introduce extra variables corresponding |
| 2631 | * to the extra integer divisions and add the div constraints |
| 2632 | * that were added to "bmap" after info->tab was created |
| 2633 | * from info->bmap. |
| 2634 | * Furthermore, check if these extra integer divisions happen |
| 2635 | * to attain a fixed integer value in info->tab. |
| 2636 | * If so, replace the corresponding div constraints by pairs |
| 2637 | * of inequality constraints that fix these |
| 2638 | * integer divisions to their single integer values. |
| 2639 | * Replace info->bmap by "bmap" to match the changes to info->tab. |
| 2640 | * info->ineq was computed without a tableau and therefore |
| 2641 | * does not take into account the redundant constraints |
| 2642 | * in the tableau. Mark them here. |
| 2643 | * There is no need to check the newly added div constraints |
| 2644 | * since they cannot be redundant. |
| 2645 | * The redundancy check is not performed when constants have been discovered |
| 2646 | * since info->ineq is completely thrown away in this case. |
| 2647 | */ |
| 2648 | static isl_stat tab_insert_divs(struct isl_coalesce_info *info, |
| 2649 | int n, struct isl_expanded *expanded, __isl_take isl_basic_map *bmap) |
| 2650 | { |
| 2651 | int i, n_ineq; |
| 2652 | unsigned n_eq; |
| 2653 | struct isl_tab_undo *snap; |
| 2654 | int any; |
| 2655 | |
| 2656 | if (!bmap) |
| 2657 | return isl_stat_error; |
| 2658 | if (info->bmap->n_eq + info->bmap->n_ineq != info->tab->n_con) |
| 2659 | isl_die(isl_basic_map_get_ctx(bmap), isl_error_internal,do { isl_handle_error(isl_basic_map_get_ctx(bmap), isl_error_internal , "original tableau does not correspond " "to original basic map" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn295388/tools/polly/lib/External/isl/isl_coalesce.c" , 2661); goto error; } while (0) |
| 2660 | "original tableau does not correspond "do { isl_handle_error(isl_basic_map_get_ctx(bmap), isl_error_internal , "original tableau does not correspond " "to original basic map" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn295388/tools/polly/lib/External/isl/isl_coalesce.c" , 2661); goto error; } while (0) |
| 2661 | "to original basic map", goto error)do { isl_handle_error(isl_basic_map_get_ctx(bmap), isl_error_internal , "original tableau does not correspond " "to original basic map" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn295388/tools/polly/lib/External/isl/isl_coalesce.c" , 2661); goto error; } while (0); |
| 2662 | |
| 2663 | if (isl_tab_extend_vars(info->tab, n) < 0) |
| 2664 | goto error; |
| 2665 | if (isl_tab_extend_cons(info->tab, 2 * n) < 0) |
| 2666 | goto error; |
| 2667 | |
| 2668 | for (i = 0; i < n; ++i) { |
| 2669 | if (isl_tab_insert_var(info->tab, expanded[i].pos) < 0) |
| 2670 | goto error; |
| 2671 | } |
| 2672 | |
| 2673 | snap = isl_tab_snap(info->tab); |
| 2674 | |
| 2675 | n_ineq = info->tab->n_con - info->tab->n_eq; |
| 2676 | if (copy_ineq(info->tab, bmap) < 0) |
| 2677 | goto error; |
| 2678 | |
| 2679 | isl_basic_map_free(info->bmap); |
| 2680 | info->bmap = bmap; |
| 2681 | |
| 2682 | any = 0; |
| 2683 | for (i = 0; i < n; ++i) { |
| 2684 | expanded[i].cst = isl_tab_is_constant(info->tab, |
| 2685 | expanded[i].pos, &expanded[i].val); |
| 2686 | if (expanded[i].cst < 0) |
| 2687 | return isl_stat_error; |
| 2688 | if (expanded[i].cst) |
| 2689 | any = 1; |
| 2690 | } |
| 2691 | |
| 2692 | if (any) { |
| 2693 | if (isl_tab_rollback(info->tab, snap) < 0) |
| 2694 | return isl_stat_error; |
| 2695 | info->bmap = isl_basic_map_cow(info->bmap); |
| 2696 | if (isl_basic_map_free_inequality(info->bmap, 2 * n) < 0) |
| 2697 | return isl_stat_error; |
| 2698 | |
| 2699 | return fix_constant_divs(info, n, expanded); |
| 2700 | } |
| 2701 | |
| 2702 | n_eq = info->bmap->n_eq; |
| 2703 | for (i = 0; i < n_ineq; ++i) { |
| 2704 | if (isl_tab_is_redundant(info->tab, n_eq + i)) |
| 2705 | info->ineq[i] = STATUS_REDUNDANT1; |
| 2706 | } |
| 2707 | |
| 2708 | return isl_stat_ok; |
| 2709 | error: |
| 2710 | isl_basic_map_free(bmap); |
| 2711 | return isl_stat_error; |
| 2712 | } |
| 2713 | |
| 2714 | /* Expand info->tab and info->bmap in the same way "bmap" was expanded |
| 2715 | * in isl_basic_map_expand_divs using the expansion "exp" and |
| 2716 | * update info->ineq with respect to the redundant constraints |
| 2717 | * in the resulting tableau. info->bmap is the original version |
| 2718 | * of "bmap", i.e., the one that corresponds to the current |
| 2719 | * state of info->tab. The number of constraints in info->bmap |
| 2720 | * is assumed to be the same as the number of constraints |
| 2721 | * in info->tab. This is required to be able to detect |
| 2722 | * the extra constraints in "bmap". |
| 2723 | * |
| 2724 | * Extract the positions where extra local variables are introduced |
| 2725 | * from "exp" and call tab_insert_divs. |
| 2726 | */ |
| 2727 | static isl_stat expand_tab(struct isl_coalesce_info *info, int *exp, |
| 2728 | __isl_take isl_basic_map *bmap) |
| 2729 | { |
| 2730 | isl_ctx *ctx; |
| 2731 | struct isl_expanded *expanded; |
| 2732 | int i, j, k, n; |
| 2733 | int extra_var; |
| 2734 | unsigned total, pos, n_div; |
| 2735 | isl_stat r; |
| 2736 | |
| 2737 | total = isl_basic_map_dim(bmap, isl_dim_all); |
| 2738 | n_div = isl_basic_map_dim(bmap, isl_dim_div); |
| 2739 | pos = total - n_div; |
| 2740 | extra_var = total - info->tab->n_var; |
| 2741 | n = n_div - extra_var; |
| 2742 | |
| 2743 | ctx = isl_basic_map_get_ctx(bmap); |
| 2744 | expanded = isl_calloc_array(ctx, struct isl_expanded, extra_var)((struct isl_expanded *)isl_calloc_or_die(ctx, extra_var, sizeof (struct isl_expanded))); |
| 2745 | if (extra_var && !expanded) |
| 2746 | goto error; |
| 2747 | |
| 2748 | i = 0; |
| 2749 | k = 0; |
| 2750 | for (j = 0; j < n_div; ++j) { |
| 2751 | if (i < n && exp[i] == j) { |
| 2752 | ++i; |
| 2753 | continue; |
| 2754 | } |
| 2755 | expanded[k++].pos = pos + j; |
| 2756 | } |
| 2757 | |
| 2758 | for (k = 0; k < extra_var; ++k) |
| 2759 | isl_int_init(expanded[k].val)isl_sioimath_init((expanded[k].val)); |
| 2760 | |
| 2761 | r = tab_insert_divs(info, extra_var, expanded, bmap); |
| 2762 | |
| 2763 | for (k = 0; k < extra_var; ++k) |
| 2764 | isl_int_clear(expanded[k].val)isl_sioimath_clear((expanded[k].val)); |
| 2765 | free(expanded); |
| 2766 | |
| 2767 | return r; |
| 2768 | error: |
| 2769 | isl_basic_map_free(bmap); |
| 2770 | return isl_stat_error; |
| 2771 | } |
| 2772 | |
| 2773 | /* Check if the union of the basic maps represented by info[i] and info[j] |
| 2774 | * can be represented by a single basic map, |
| 2775 | * after expanding the divs of info[i] to match those of info[j]. |
| 2776 | * If so, replace the pair by the single basic map and return |
| 2777 | * isl_change_drop_first, isl_change_drop_second or isl_change_fuse. |
| 2778 | * Otherwise, return isl_change_none. |
| 2779 | * |
| 2780 | * The caller has already checked for info[j] being a subset of info[i]. |
| 2781 | * If some of the divs of info[j] are unknown, then the expanded info[i] |
| 2782 | * will not have the corresponding div constraints. The other patterns |
| 2783 | * therefore cannot apply. Skip the computation in this case. |
| 2784 | * |
| 2785 | * The expansion is performed using the divs "div" and expansion "exp" |
| 2786 | * computed by the caller. |
| 2787 | * info[i].bmap has already been expanded and the result is passed in |
| 2788 | * as "bmap". |
| 2789 | * The "eq" and "ineq" fields of info[i] reflect the status of |
| 2790 | * the constraints of the expanded "bmap" with respect to info[j].tab. |
| 2791 | * However, inequality constraints that are redundant in info[i].tab |
| 2792 | * have not yet been marked as such because no tableau was available. |
| 2793 | * |
| 2794 | * Replace info[i].bmap by "bmap" and expand info[i].tab as well, |
| 2795 | * updating info[i].ineq with respect to the redundant constraints. |
| 2796 | * Then try and coalesce the expanded info[i] with info[j], |
| 2797 | * reusing the information in info[i].eq and info[i].ineq. |
| 2798 | * If this does not result in any coalescing or if it results in info[j] |
| 2799 | * getting dropped (which should not happen in practice, since the case |
| 2800 | * of info[j] being a subset of info[i] has already been checked by |
| 2801 | * the caller), then revert info[i] to its original state. |
| 2802 | */ |
| 2803 | static enum isl_change coalesce_expand_tab_divs(__isl_take isl_basic_map *bmap, |
| 2804 | int i, int j, struct isl_coalesce_info *info, __isl_keep isl_mat *div, |
| 2805 | int *exp) |
| 2806 | { |
| 2807 | isl_bool known; |
| 2808 | isl_basic_map *bmap_i; |
| 2809 | struct isl_tab_undo *snap; |
| 2810 | enum isl_change change = isl_change_none; |
| 2811 | |
| 2812 | known = isl_basic_map_divs_known(info[j].bmap); |
| 2813 | if (known < 0 || !known) { |
| 2814 | clear_status(&info[i]); |
| 2815 | isl_basic_map_free(bmap); |
| 2816 | return known < 0 ? isl_change_error : isl_change_none; |
| 2817 | } |
| 2818 | |
| 2819 | bmap_i = isl_basic_map_copy(info[i].bmap); |
| 2820 | snap = isl_tab_snap(info[i].tab); |
| 2821 | if (expand_tab(&info[i], exp, bmap) < 0) |
| 2822 | change = isl_change_error; |
| 2823 | |
| 2824 | init_status(&info[j]); |
| 2825 | if (change == isl_change_none) |
| 2826 | change = coalesce_local_pair_reuse(i, j, info); |
| 2827 | else |
| 2828 | clear_status(&info[i]); |
| 2829 | if (change != isl_change_none && change != isl_change_drop_second) { |
| 2830 | isl_basic_map_free(bmap_i); |
| 2831 | } else { |
| 2832 | isl_basic_map_free(info[i].bmap); |
| 2833 | info[i].bmap = bmap_i; |
| 2834 | |
| 2835 | if (isl_tab_rollback(info[i].tab, snap) < 0) |
| 2836 | change = isl_change_error; |
| 2837 | } |
| 2838 | |
| 2839 | return change; |
| 2840 | } |
| 2841 | |
| 2842 | /* Check if the union of "bmap" and the basic map represented by info[j] |
| 2843 | * can be represented by a single basic map, |
| 2844 | * after expanding the divs of "bmap" to match those of info[j]. |
| 2845 | * If so, replace the pair by the single basic map and return |
| 2846 | * isl_change_drop_first, isl_change_drop_second or isl_change_fuse. |
| 2847 | * Otherwise, return isl_change_none. |
| 2848 | * |
| 2849 | * In particular, check if the expanded "bmap" contains the basic map |
| 2850 | * represented by the tableau info[j].tab. |
| 2851 | * The expansion is performed using the divs "div" and expansion "exp" |
| 2852 | * computed by the caller. |
| 2853 | * Then we check if all constraints of the expanded "bmap" are valid for |
| 2854 | * info[j].tab. |
| 2855 | * |
| 2856 | * If "i" is not equal to -1, then "bmap" is equal to info[i].bmap. |
| 2857 | * In this case, the positions of the constraints of info[i].bmap |
| 2858 | * with respect to the basic map represented by info[j] are stored |
| 2859 | * in info[i]. |
| 2860 | * |
| 2861 | * If the expanded "bmap" does not contain the basic map |
| 2862 | * represented by the tableau info[j].tab and if "i" is not -1, |
| 2863 | * i.e., if the original "bmap" is info[i].bmap, then expand info[i].tab |
| 2864 | * as well and check if that results in coalescing. |
| 2865 | */ |
| 2866 | static enum isl_change coalesce_with_expanded_divs( |
| 2867 | __isl_keep isl_basic_map *bmap, int i, int j, |
| 2868 | struct isl_coalesce_info *info, __isl_keep isl_mat *div, int *exp) |
| 2869 | { |
| 2870 | enum isl_change change = isl_change_none; |
| 2871 | struct isl_coalesce_info info_local, *info_i; |
| 2872 | |
| 2873 | info_i = i >= 0 ? &info[i] : &info_local; |
| 2874 | init_status(info_i); |
| 2875 | bmap = isl_basic_map_copy(bmap); |
| 2876 | bmap = isl_basic_map_expand_divs(bmap, isl_mat_copy(div), exp); |
| 2877 | bmap = isl_basic_map_mark_final(bmap); |
| 2878 | |
| 2879 | if (!bmap) |
| 2880 | goto error; |
| 2881 | |
| 2882 | info_i->eq = eq_status_in(bmap, info[j].tab); |
| 2883 | if (bmap->n_eq && !info_i->eq) |
| 2884 | goto error; |
| 2885 | if (any(info_i->eq, 2 * bmap->n_eq, STATUS_ERROR-1)) |
| 2886 | goto error; |
| 2887 | if (any(info_i->eq, 2 * bmap->n_eq, STATUS_SEPARATE3)) |
| 2888 | goto done; |
| 2889 | |
| 2890 | info_i->ineq = ineq_status_in(bmap, NULL((void*)0), info[j].tab); |
| 2891 | if (bmap->n_ineq && !info_i->ineq) |
| 2892 | goto error; |
| 2893 | if (any(info_i->ineq, bmap->n_ineq, STATUS_ERROR-1)) |
| 2894 | goto error; |
| 2895 | if (any(info_i->ineq, bmap->n_ineq, STATUS_SEPARATE3)) |
| 2896 | goto done; |
| 2897 | |
| 2898 | if (all(info_i->eq, 2 * bmap->n_eq, STATUS_VALID2) && |
| 2899 | all(info_i->ineq, bmap->n_ineq, STATUS_VALID2)) { |
| 2900 | drop(&info[j]); |
| 2901 | change = isl_change_drop_second; |
| 2902 | } |
| 2903 | |
| 2904 | if (change == isl_change_none && i != -1) |
| 2905 | return coalesce_expand_tab_divs(bmap, i, j, info, div, exp); |
| 2906 | |
| 2907 | done: |
| 2908 | isl_basic_map_free(bmap); |
| 2909 | clear_status(info_i); |
| 2910 | return change; |
| 2911 | error: |
| 2912 | isl_basic_map_free(bmap); |
| 2913 | clear_status(info_i); |
| 2914 | return isl_change_error; |
| 2915 | } |
| 2916 | |
| 2917 | /* Check if the union of "bmap_i" and the basic map represented by info[j] |
| 2918 | * can be represented by a single basic map, |
| 2919 | * after aligning the divs of "bmap_i" to match those of info[j]. |
| 2920 | * If so, replace the pair by the single basic map and return |
| 2921 | * isl_change_drop_first, isl_change_drop_second or isl_change_fuse. |
| 2922 | * Otherwise, return isl_change_none. |
| 2923 | * |
| 2924 | * In particular, check if "bmap_i" contains the basic map represented by |
| 2925 | * info[j] after aligning the divs of "bmap_i" to those of info[j]. |
| 2926 | * Note that this can only succeed if the number of divs of "bmap_i" |
| 2927 | * is smaller than (or equal to) the number of divs of info[j]. |
| 2928 | * |
| 2929 | * We first check if the divs of "bmap_i" are all known and form a subset |
| 2930 | * of those of info[j].bmap. If so, we pass control over to |
| 2931 | * coalesce_with_expanded_divs. |
| 2932 | * |
| 2933 | * If "i" is not equal to -1, then "bmap" is equal to info[i].bmap. |
| 2934 | */ |
| 2935 | static enum isl_change coalesce_after_aligning_divs( |
| 2936 | __isl_keep isl_basic_map *bmap_i, int i, int j, |
| 2937 | struct isl_coalesce_info *info) |
| 2938 | { |
| 2939 | int known; |
| 2940 | isl_mat *div_i, *div_j, *div; |
| 2941 | int *exp1 = NULL((void*)0); |
| 2942 | int *exp2 = NULL((void*)0); |
| 2943 | isl_ctx *ctx; |
| 2944 | enum isl_change change; |
| 2945 | |
| 2946 | known = isl_basic_map_divs_known(bmap_i); |
| 2947 | if (known < 0 || !known) |
| 2948 | return known; |
| 2949 | |
| 2950 | ctx = isl_basic_map_get_ctx(bmap_i); |
| 2951 | |
| 2952 | div_i = isl_basic_map_get_divs(bmap_i); |
| 2953 | div_j = isl_basic_map_get_divs(info[j].bmap); |
| 2954 | |
| 2955 | if (!div_i || !div_j) |
| 2956 | goto error; |
| 2957 | |
| 2958 | exp1 = isl_alloc_array(ctx, int, div_i->n_row)((int *)isl_malloc_or_die(ctx, (div_i->n_row)*sizeof(int)) ); |
| 2959 | exp2 = isl_alloc_array(ctx, int, div_j->n_row)((int *)isl_malloc_or_die(ctx, (div_j->n_row)*sizeof(int)) ); |
| 2960 | if ((div_i->n_row && !exp1) || (div_j->n_row && !exp2)) |
| 2961 | goto error; |
| 2962 | |
| 2963 | div = isl_merge_divs(div_i, div_j, exp1, exp2); |
| 2964 | if (!div) |
| 2965 | goto error; |
| 2966 | |
| 2967 | if (div->n_row == div_j->n_row) |
| 2968 | change = coalesce_with_expanded_divs(bmap_i, |
| 2969 | i, j, info, div, exp1); |
| 2970 | else |
| 2971 | change = isl_change_none; |
| 2972 | |
| 2973 | isl_mat_free(div); |
| 2974 | |
| 2975 | isl_mat_free(div_i); |
| 2976 | isl_mat_free(div_j); |
| 2977 | |
| 2978 | free(exp2); |
| 2979 | free(exp1); |
| 2980 | |
| 2981 | return change; |
| 2982 | error: |
| 2983 | isl_mat_free(div_i); |
| 2984 | isl_mat_free(div_j); |
| 2985 | free(exp1); |
| 2986 | free(exp2); |
| 2987 | return isl_change_error; |
| 2988 | } |
| 2989 | |
| 2990 | /* Check if basic map "j" is a subset of basic map "i" after |
| 2991 | * exploiting the extra equalities of "j" to simplify the divs of "i". |
| 2992 | * If so, remove basic map "j" and return isl_change_drop_second. |
| 2993 | * |
| 2994 | * If "j" does not have any equalities or if they are the same |
| 2995 | * as those of "i", then we cannot exploit them to simplify the divs. |
| 2996 | * Similarly, if there are no divs in "i", then they cannot be simplified. |
| 2997 | * If, on the other hand, the affine hulls of "i" and "j" do not intersect, |
| 2998 | * then "j" cannot be a subset of "i". |
| 2999 | * |
| 3000 | * Otherwise, we intersect "i" with the affine hull of "j" and then |
| 3001 | * check if "j" is a subset of the result after aligning the divs. |
| 3002 | * If so, then "j" is definitely a subset of "i" and can be removed. |
| 3003 | * Note that if after intersection with the affine hull of "j". |
| 3004 | * "i" still has more divs than "j", then there is no way we can |
| 3005 | * align the divs of "i" to those of "j". |
| 3006 | */ |
| 3007 | static enum isl_change coalesce_subset_with_equalities(int i, int j, |
| 3008 | struct isl_coalesce_info *info) |
| 3009 | { |
| 3010 | isl_basic_map *hull_i, *hull_j, *bmap_i; |
| 3011 | int equal, empty; |
| 3012 | enum isl_change change; |
| 3013 | |
| 3014 | if (info[j].bmap->n_eq == 0) |
| 3015 | return isl_change_none; |
| 3016 | if (info[i].bmap->n_div == 0) |
| 3017 | return isl_change_none; |
| 3018 | |
| 3019 | hull_i = isl_basic_map_copy(info[i].bmap); |
| 3020 | hull_i = isl_basic_map_plain_affine_hull(hull_i); |
| 3021 | hull_j = isl_basic_map_copy(info[j].bmap); |
| 3022 | hull_j = isl_basic_map_plain_affine_hull(hull_j); |
| 3023 | |
| 3024 | hull_j = isl_basic_map_intersect(hull_j, isl_basic_map_copy(hull_i)); |
| 3025 | equal = isl_basic_map_plain_is_equal(hull_i, hull_j); |
| 3026 | empty = isl_basic_map_plain_is_empty(hull_j); |
| 3027 | isl_basic_map_free(hull_i); |
| 3028 | |
| 3029 | if (equal < 0 || equal || empty < 0 || empty) { |
| 3030 | isl_basic_map_free(hull_j); |
| 3031 | if (equal < 0 || empty < 0) |
| 3032 | return isl_change_error; |
| 3033 | return isl_change_none; |
| 3034 | } |
| 3035 | |
| 3036 | bmap_i = isl_basic_map_copy(info[i].bmap); |
| 3037 | bmap_i = isl_basic_map_intersect(bmap_i, hull_j); |
| 3038 | if (!bmap_i) |
| 3039 | return isl_change_error; |
| 3040 | |
| 3041 | if (bmap_i->n_div > info[j].bmap->n_div) { |
| 3042 | isl_basic_map_free(bmap_i); |
| 3043 | return isl_change_none; |
| 3044 | } |
| 3045 | |
| 3046 | change = coalesce_after_aligning_divs(bmap_i, -1, j, info); |
| 3047 | |
| 3048 | isl_basic_map_free(bmap_i); |
| 3049 | |
| 3050 | return change; |
| 3051 | } |
| 3052 | |
| 3053 | /* Check if the union of and the basic maps represented by info[i] and info[j] |
| 3054 | * can be represented by a single basic map, by aligning or equating |
| 3055 | * their integer divisions. |
| 3056 | * If so, replace the pair by the single basic map and return |
| 3057 | * isl_change_drop_first, isl_change_drop_second or isl_change_fuse. |
| 3058 | * Otherwise, return isl_change_none. |
| 3059 | * |
| 3060 | * Note that we only perform any test if the number of divs is different |
| 3061 | * in the two basic maps. In case the number of divs is the same, |
| 3062 | * we have already established that the divs are different |
| 3063 | * in the two basic maps. |
| 3064 | * In particular, if the number of divs of basic map i is smaller than |
| 3065 | * the number of divs of basic map j, then we check if j is a subset of i |
| 3066 | * and vice versa. |
| 3067 | */ |
| 3068 | static enum isl_change coalesce_divs(int i, int j, |
| 3069 | struct isl_coalesce_info *info) |
| 3070 | { |
| 3071 | enum isl_change change = isl_change_none; |
| 3072 | |
| 3073 | if (info[i].bmap->n_div < info[j].bmap->n_div) |
| 3074 | change = coalesce_after_aligning_divs(info[i].bmap, i, j, info); |
| 3075 | if (change != isl_change_none) |
| 3076 | return change; |
| 3077 | |
| 3078 | if (info[j].bmap->n_div < info[i].bmap->n_div) |
| 3079 | change = coalesce_after_aligning_divs(info[j].bmap, j, i, info); |
| 3080 | if (change != isl_change_none) |
| 3081 | return invert_change(change); |
| 3082 | |
| 3083 | change = coalesce_subset_with_equalities(i, j, info); |
| 3084 | if (change != isl_change_none) |
| 3085 | return change; |
| 3086 | |
| 3087 | change = coalesce_subset_with_equalities(j, i, info); |
| 3088 | if (change != isl_change_none) |
| 3089 | return invert_change(change); |
| 3090 | |
| 3091 | return isl_change_none; |
| 3092 | } |
| 3093 | |
| 3094 | /* Does "bmap" involve any divs that themselves refer to divs? |
| 3095 | */ |
| 3096 | static int has_nested_div(__isl_keep isl_basic_map *bmap) |
| 3097 | { |
| 3098 | int i; |
| 3099 | unsigned total; |
| 3100 | unsigned n_div; |
| 3101 | |
| 3102 | total = isl_basic_map_dim(bmap, isl_dim_all); |
| 3103 | n_div = isl_basic_map_dim(bmap, isl_dim_div); |
| 3104 | total -= n_div; |
| 3105 | |
| 3106 | for (i = 0; i < n_div; ++i) |
| 3107 | if (isl_seq_first_non_zero(bmap->div[i] + 2 + total, |
| 3108 | n_div) != -1) |
| 3109 | return 1; |
| 3110 | |
| 3111 | return 0; |
| 3112 | } |
| 3113 | |
| 3114 | /* Return a list of affine expressions, one for each integer division |
| 3115 | * in "bmap_i". For each integer division that also appears in "bmap_j", |
| 3116 | * the affine expression is set to NaN. The number of NaNs in the list |
| 3117 | * is equal to the number of integer divisions in "bmap_j". |
| 3118 | * For the other integer divisions of "bmap_i", the corresponding |
| 3119 | * element in the list is a purely affine expression equal to the integer |
| 3120 | * division in "hull". |
| 3121 | * If no such list can be constructed, then the number of elements |
| 3122 | * in the returned list is smaller than the number of integer divisions |
| 3123 | * in "bmap_i". |
| 3124 | */ |
| 3125 | static __isl_give isl_aff_list *set_up_substitutions( |
| 3126 | __isl_keep isl_basic_map *bmap_i, __isl_keep isl_basic_map *bmap_j, |
| 3127 | __isl_take isl_basic_map *hull) |
| 3128 | { |
| 3129 | unsigned n_div_i, n_div_j, total; |
| 3130 | isl_ctx *ctx; |
| 3131 | isl_local_space *ls; |
| 3132 | isl_basic_setisl_basic_map *wrap_hull; |
| 3133 | isl_aff *aff_nan; |
| 3134 | isl_aff_list *list; |
| 3135 | int i, j; |
| 3136 | |
| 3137 | if (!hull) |
| 3138 | return NULL((void*)0); |
| 3139 | |
| 3140 | ctx = isl_basic_map_get_ctx(hull); |
| 3141 | |
| 3142 | n_div_i = isl_basic_map_dim(bmap_i, isl_dim_div); |
| 3143 | n_div_j = isl_basic_map_dim(bmap_j, isl_dim_div); |
| 3144 | total = isl_basic_map_total_dim(bmap_i) - n_div_i; |
| 3145 | |
| 3146 | ls = isl_basic_map_get_local_space(bmap_i); |
| 3147 | ls = isl_local_space_wrap(ls); |
| 3148 | wrap_hull = isl_basic_map_wrap(hull); |
| 3149 | |
| 3150 | aff_nan = isl_aff_nan_on_domain(isl_local_space_copy(ls)); |
| 3151 | list = isl_aff_list_alloc(ctx, n_div_i); |
| 3152 | |
| 3153 | j = 0; |
| 3154 | for (i = 0; i < n_div_i; ++i) { |
| 3155 | isl_aff *aff; |
| 3156 | |
| 3157 | if (j < n_div_j && |
| 3158 | isl_basic_map_equal_div_expr_part(bmap_i, i, bmap_j, j, |
| 3159 | 0, 2 + total)) { |
| 3160 | ++j; |
| 3161 | list = isl_aff_list_add(list, isl_aff_copy(aff_nan)); |
| 3162 | continue; |
| 3163 | } |
| 3164 | if (n_div_i - i <= n_div_j - j) |
| 3165 | break; |
| 3166 | |
| 3167 | aff = isl_local_space_get_div(ls, i); |
| 3168 | aff = isl_aff_substitute_equalities(aff, |
| 3169 | isl_basic_set_copy(wrap_hull)); |
| 3170 | aff = isl_aff_floor(aff); |
| 3171 | if (!aff) |
| 3172 | goto error; |
| 3173 | if (isl_aff_dim(aff, isl_dim_div) != 0) { |
| 3174 | isl_aff_free(aff); |
| 3175 | break; |
| 3176 | } |
| 3177 | |
| 3178 | list = isl_aff_list_add(list, aff); |
| 3179 | } |
| 3180 | |
| 3181 | isl_aff_free(aff_nan); |
| 3182 | isl_local_space_free(ls); |
| 3183 | isl_basic_set_free(wrap_hull); |
| 3184 | |
| 3185 | return list; |
| 3186 | error: |
| 3187 | isl_aff_free(aff_nan); |
| 3188 | isl_local_space_free(ls); |
| 3189 | isl_basic_set_free(wrap_hull); |
| 3190 | isl_aff_list_free(list); |
| 3191 | return NULL((void*)0); |
| 3192 | } |
| 3193 | |
| 3194 | /* Add variables to info->bmap and info->tab corresponding to the elements |
| 3195 | * in "list" that are not set to NaN. |
| 3196 | * "extra_var" is the number of these elements. |
| 3197 | * "dim" is the offset in the variables of "tab" where we should |
| 3198 | * start considering the elements in "list". |
| 3199 | * When this function returns, the total number of variables in "tab" |
| 3200 | * is equal to "dim" plus the number of elements in "list". |
| 3201 | * |
| 3202 | * The newly added existentially quantified variables are not given |
| 3203 | * an explicit representation because the corresponding div constraints |
| 3204 | * do not appear in info->bmap. These constraints are not added |
| 3205 | * to info->bmap because for internal consistency, they would need to |
| 3206 | * be added to info->tab as well, where they could combine with the equality |
| 3207 | * that is added later to result in constraints that do not hold |
| 3208 | * in the original input. |
| 3209 | */ |
| 3210 | static int add_sub_vars(struct isl_coalesce_info *info, |
| 3211 | __isl_keep isl_aff_list *list, int dim, int extra_var) |
| 3212 | { |
| 3213 | int i, j, n, d; |
| 3214 | isl_space *space; |
| 3215 | |
| 3216 | space = isl_basic_map_get_space(info->bmap); |
| 3217 | info->bmap = isl_basic_map_cow(info->bmap); |
| 3218 | info->bmap = isl_basic_map_extend_space(info->bmap, space, |
| 3219 | extra_var, 0, 0); |
| 3220 | if (!info->bmap) |
| 3221 | return -1; |
| 3222 | n = isl_aff_list_n_aff(list); |
| 3223 | for (i = 0; i < n; ++i) { |
| 3224 | int is_nan; |
| 3225 | isl_aff *aff; |
| 3226 | |
| 3227 | aff = isl_aff_list_get_aff(list, i); |
| 3228 | is_nan = isl_aff_is_nan(aff); |
| 3229 | isl_aff_free(aff); |
| 3230 | if (is_nan < 0) |
| 3231 | return -1; |
| 3232 | if (is_nan) |
| 3233 | continue; |
| 3234 | |
| 3235 | if (isl_tab_insert_var(info->tab, dim + i) < 0) |
| 3236 | return -1; |
| 3237 | d = isl_basic_map_alloc_div(info->bmap); |
| 3238 | if (d < 0) |
| 3239 | return -1; |
| 3240 | info->bmap = isl_basic_map_mark_div_unknown(info->bmap, d); |
| 3241 | if (!info->bmap) |
| 3242 | return -1; |
| 3243 | for (j = d; j > i; --j) |
| 3244 | isl_basic_map_swap_div(info->bmap, j - 1, j); |
| 3245 | } |
| 3246 | |
| 3247 | return 0; |
| 3248 | } |
| 3249 | |
| 3250 | /* For each element in "list" that is not set to NaN, fix the corresponding |
| 3251 | * variable in "tab" to the purely affine expression defined by the element. |
| 3252 | * "dim" is the offset in the variables of "tab" where we should |
| 3253 | * start considering the elements in "list". |
| 3254 | * |
| 3255 | * This function assumes that a sufficient number of rows and |
| 3256 | * elements in the constraint array are available in the tableau. |
| 3257 | */ |
| 3258 | static int add_sub_equalities(struct isl_tab *tab, |
| 3259 | __isl_keep isl_aff_list *list, int dim) |
| 3260 | { |
| 3261 | int i, n; |
| 3262 | isl_ctx *ctx; |
| 3263 | isl_vec *sub; |
| 3264 | isl_aff *aff; |
| 3265 | |
| 3266 | n = isl_aff_list_n_aff(list); |
| 3267 | |
| 3268 | ctx = isl_tab_get_ctx(tab); |
| 3269 | sub = isl_vec_alloc(ctx, 1 + dim + n); |
| 3270 | if (!sub) |
| 3271 | return -1; |
| 3272 | isl_seq_clr(sub->el + 1 + dim, n); |
| 3273 | |
| 3274 | for (i = 0; i < n; ++i) { |
| 3275 | aff = isl_aff_list_get_aff(list, i); |
| 3276 | if (!aff) |
| 3277 | goto error; |
| 3278 | if (isl_aff_is_nan(aff)) { |
| 3279 | isl_aff_free(aff); |
| 3280 | continue; |
| 3281 | } |
| 3282 | isl_seq_cpy(sub->el, aff->v->el + 1, 1 + dim); |
| 3283 | isl_int_neg(sub->el[1 + dim + i], aff->v->el[0])isl_sioimath_neg((sub->el[1 + dim + i]), *(aff->v->el [0])); |
| 3284 | if (isl_tab_add_eq(tab, sub->el) < 0) |
| 3285 | goto error; |
| 3286 | isl_int_set_si(sub->el[1 + dim + i], 0)isl_sioimath_set_si((sub->el[1 + dim + i]), 0); |
| 3287 | isl_aff_free(aff); |
| 3288 | } |
| 3289 | |
| 3290 | isl_vec_free(sub); |
| 3291 | return 0; |
| 3292 | error: |
| 3293 | isl_aff_free(aff); |
| 3294 | isl_vec_free(sub); |
| 3295 | return -1; |
| 3296 | } |
| 3297 | |
| 3298 | /* Add variables to info->tab and info->bmap corresponding to the elements |
| 3299 | * in "list" that are not set to NaN. The value of the added variable |
| 3300 | * in info->tab is fixed to the purely affine expression defined by the element. |
| 3301 | * "dim" is the offset in the variables of info->tab where we should |
| 3302 | * start considering the elements in "list". |
| 3303 | * When this function returns, the total number of variables in info->tab |
| 3304 | * is equal to "dim" plus the number of elements in "list". |
| 3305 | */ |
| 3306 | static int add_subs(struct isl_coalesce_info *info, |
| 3307 | __isl_keep isl_aff_list *list, int dim) |
| 3308 | { |
| 3309 | int extra_var; |
| 3310 | int n; |
| 3311 | |
| 3312 | if (!list) |
| 3313 | return -1; |
| 3314 | |
| 3315 | n = isl_aff_list_n_aff(list); |
| 3316 | extra_var = n - (info->tab->n_var - dim); |
| 3317 | |
| 3318 | if (isl_tab_extend_vars(info->tab, extra_var) < 0) |
| 3319 | return -1; |
| 3320 | if (isl_tab_extend_cons(info->tab, 2 * extra_var) < 0) |
| 3321 | return -1; |
| 3322 | if (add_sub_vars(info, list, dim, extra_var) < 0) |
| 3323 | return -1; |
| 3324 | |
| 3325 | return add_sub_equalities(info->tab, list, dim); |
| 3326 | } |
| 3327 | |
| 3328 | /* Coalesce basic map "j" into basic map "i" after adding the extra integer |
| 3329 | * divisions in "i" but not in "j" to basic map "j", with values |
| 3330 | * specified by "list". The total number of elements in "list" |
| 3331 | * is equal to the number of integer divisions in "i", while the number |
| 3332 | * of NaN elements in the list is equal to the number of integer divisions |
| 3333 | * in "j". |
| 3334 | * |
| 3335 | * If no coalescing can be performed, then we need to revert basic map "j" |
| 3336 | * to its original state. We do the same if basic map "i" gets dropped |
| 3337 | * during the coalescing, even though this should not happen in practice |
| 3338 | * since we have already checked for "j" being a subset of "i" |
| 3339 | * before we reach this stage. |
| 3340 | */ |
| 3341 | static enum isl_change coalesce_with_subs(int i, int j, |
| 3342 | struct isl_coalesce_info *info, __isl_keep isl_aff_list *list) |
| 3343 | { |
| 3344 | isl_basic_map *bmap_j; |
| 3345 | struct isl_tab_undo *snap; |
| 3346 | unsigned dim; |
| 3347 | enum isl_change change; |
| 3348 | |
| 3349 | bmap_j = isl_basic_map_copy(info[j].bmap); |
| 3350 | snap = isl_tab_snap(info[j].tab); |
| 3351 | |
| 3352 | dim = isl_basic_map_dim(bmap_j, isl_dim_all); |
| 3353 | dim -= isl_basic_map_dim(bmap_j, isl_dim_div); |
| 3354 | if (add_subs(&info[j], list, dim) < 0) |
| 3355 | goto error; |
| 3356 | |
| 3357 | change = coalesce_local_pair(i, j, info); |
| 3358 | if (change != isl_change_none && change != isl_change_drop_first) { |
| 3359 | isl_basic_map_free(bmap_j); |
| 3360 | } else { |
| 3361 | isl_basic_map_free(info[j].bmap); |
| 3362 | info[j].bmap = bmap_j; |
| 3363 | |
| 3364 | if (isl_tab_rollback(info[j].tab, snap) < 0) |
| 3365 | return isl_change_error; |
| 3366 | } |
| 3367 | |
| 3368 | return change; |
| 3369 | error: |
| 3370 | isl_basic_map_free(bmap_j); |
| 3371 | return isl_change_error; |
| 3372 | } |
| 3373 | |
| 3374 | /* Check if we can coalesce basic map "j" into basic map "i" after copying |
| 3375 | * those extra integer divisions in "i" that can be simplified away |
| 3376 | * using the extra equalities in "j". |
| 3377 | * All divs are assumed to be known and not contain any nested divs. |
| 3378 | * |
| 3379 | * We first check if there are any extra equalities in "j" that we |
| 3380 | * can exploit. Then we check if every integer division in "i" |
| 3381 | * either already appears in "j" or can be simplified using the |
| 3382 | * extra equalities to a purely affine expression. |
| 3383 | * If these tests succeed, then we try to coalesce the two basic maps |
| 3384 | * by introducing extra dimensions in "j" corresponding to |
| 3385 | * the extra integer divsisions "i" fixed to the corresponding |
| 3386 | * purely affine expression. |
| 3387 | */ |
| 3388 | static enum isl_change check_coalesce_into_eq(int i, int j, |
| 3389 | struct isl_coalesce_info *info) |
| 3390 | { |
| 3391 | unsigned n_div_i, n_div_j; |
| 3392 | isl_basic_map *hull_i, *hull_j; |
| 3393 | int equal, empty; |
| 3394 | isl_aff_list *list; |
| 3395 | enum isl_change change; |
| 3396 | |
| 3397 | n_div_i = isl_basic_map_dim(info[i].bmap, isl_dim_div); |
| 3398 | n_div_j = isl_basic_map_dim(info[j].bmap, isl_dim_div); |
| 3399 | if (n_div_i <= n_div_j) |
| 3400 | return isl_change_none; |
| 3401 | if (info[j].bmap->n_eq == 0) |
| 3402 | return isl_change_none; |
| 3403 | |
| 3404 | hull_i = isl_basic_map_copy(info[i].bmap); |
| 3405 | hull_i = isl_basic_map_plain_affine_hull(hull_i); |
| 3406 | hull_j = isl_basic_map_copy(info[j].bmap); |
| 3407 | hull_j = isl_basic_map_plain_affine_hull(hull_j); |
| 3408 | |
| 3409 | hull_j = isl_basic_map_intersect(hull_j, isl_basic_map_copy(hull_i)); |
| 3410 | equal = isl_basic_map_plain_is_equal(hull_i, hull_j); |
| 3411 | empty = isl_basic_map_plain_is_empty(hull_j); |
| 3412 | isl_basic_map_free(hull_i); |
| 3413 | |
| 3414 | if (equal < 0 || empty < 0) |
| 3415 | goto error; |
| 3416 | if (equal || empty) { |
| 3417 | isl_basic_map_free(hull_j); |
| 3418 | return isl_change_none; |
| 3419 | } |
| 3420 | |
| 3421 | list = set_up_substitutions(info[i].bmap, info[j].bmap, hull_j); |
| 3422 | if (!list) |
| 3423 | return isl_change_error; |
| 3424 | if (isl_aff_list_n_aff(list) < n_div_i) |
| 3425 | change = isl_change_none; |
| 3426 | else |
| 3427 | change = coalesce_with_subs(i, j, info, list); |
| 3428 | |
| 3429 | isl_aff_list_free(list); |
| 3430 | |
| 3431 | return change; |
| 3432 | error: |
| 3433 | isl_basic_map_free(hull_j); |
| 3434 | return isl_change_error; |
| 3435 | } |
| 3436 | |
| 3437 | /* Check if we can coalesce basic maps "i" and "j" after copying |
| 3438 | * those extra integer divisions in one of the basic maps that can |
| 3439 | * be simplified away using the extra equalities in the other basic map. |
| 3440 | * We require all divs to be known in both basic maps. |
| 3441 | * Furthermore, to simplify the comparison of div expressions, |
| 3442 | * we do not allow any nested integer divisions. |
| 3443 | */ |
| 3444 | static enum isl_change check_coalesce_eq(int i, int j, |
| 3445 | struct isl_coalesce_info *info) |
| 3446 | { |
| 3447 | int known, nested; |
| 3448 | enum isl_change change; |
| 3449 | |
| 3450 | known = isl_basic_map_divs_known(info[i].bmap); |
| 3451 | if (known < 0 || !known) |
| 3452 | return known < 0 ? isl_change_error : isl_change_none; |
| 3453 | known = isl_basic_map_divs_known(info[j].bmap); |
| 3454 | if (known < 0 || !known) |
| 3455 | return known < 0 ? isl_change_error : isl_change_none; |
| 3456 | nested = has_nested_div(info[i].bmap); |
| 3457 | if (nested < 0 || nested) |
| 3458 | return nested < 0 ? isl_change_error : isl_change_none; |
| 3459 | nested = has_nested_div(info[j].bmap); |
| 3460 | if (nested < 0 || nested) |
| 3461 | return nested < 0 ? isl_change_error : isl_change_none; |
| 3462 | |
| 3463 | change = check_coalesce_into_eq(i, j, info); |
| 3464 | if (change != isl_change_none) |
| 3465 | return change; |
| 3466 | change = check_coalesce_into_eq(j, i, info); |
| 3467 | if (change != isl_change_none) |
| 3468 | return invert_change(change); |
| 3469 | |
| 3470 | return isl_change_none; |
| 3471 | } |
| 3472 | |
| 3473 | /* Check if the union of the given pair of basic maps |
| 3474 | * can be represented by a single basic map. |
| 3475 | * If so, replace the pair by the single basic map and return |
| 3476 | * isl_change_drop_first, isl_change_drop_second or isl_change_fuse. |
| 3477 | * Otherwise, return isl_change_none. |
| 3478 | * |
| 3479 | * We first check if the two basic maps live in the same local space, |
| 3480 | * after aligning the divs that differ by only an integer constant. |
| 3481 | * If so, we do the complete check. Otherwise, we check if they have |
| 3482 | * the same number of integer divisions and can be coalesced, if one is |
| 3483 | * an obvious subset of the other or if the extra integer divisions |
| 3484 | * of one basic map can be simplified away using the extra equalities |
| 3485 | * of the other basic map. |
| 3486 | */ |
| 3487 | static enum isl_change coalesce_pair(int i, int j, |
| 3488 | struct isl_coalesce_info *info) |
| 3489 | { |
| 3490 | int same; |
| 3491 | enum isl_change change; |
| 3492 | |
| 3493 | if (harmonize_divs(&info[i], &info[j]) < 0) |
| 3494 | return isl_change_error; |
| 3495 | same = same_divs(info[i].bmap, info[j].bmap); |
| 3496 | if (same < 0) |
| 3497 | return isl_change_error; |
| 3498 | if (same) |
| 3499 | return coalesce_local_pair(i, j, info); |
| 3500 | |
| 3501 | if (info[i].bmap->n_div == info[j].bmap->n_div) { |
| 3502 | change = coalesce_local_pair(i, j, info); |
| 3503 | if (change != isl_change_none) |
| 3504 | return change; |
| 3505 | } |
| 3506 | |
| 3507 | change = coalesce_divs(i, j, info); |
| 3508 | if (change != isl_change_none) |
| 3509 | return change; |
| 3510 | |
| 3511 | return check_coalesce_eq(i, j, info); |
| 3512 | } |
| 3513 | |
| 3514 | /* Return the maximum of "a" and "b". |
| 3515 | */ |
| 3516 | static int isl_max(int a, int b) |
| 3517 | { |
| 3518 | return a > b ? a : b; |
| 3519 | } |
| 3520 | |
| 3521 | /* Pairwise coalesce the basic maps in the range [start1, end1[ of "info" |
| 3522 | * with those in the range [start2, end2[, skipping basic maps |
| 3523 | * that have been removed (either before or within this function). |
| 3524 | * |
| 3525 | * For each basic map i in the first range, we check if it can be coalesced |
| 3526 | * with respect to any previously considered basic map j in the second range. |
| 3527 | * If i gets dropped (because it was a subset of some j), then |
| 3528 | * we can move on to the next basic map. |
| 3529 | * If j gets dropped, we need to continue checking against the other |
| 3530 | * previously considered basic maps. |
| 3531 | * If the two basic maps got fused, then we recheck the fused basic map |
| 3532 | * against the previously considered basic maps, starting at i + 1 |
| 3533 | * (even if start2 is greater than i + 1). |
| 3534 | */ |
| 3535 | static int coalesce_range(isl_ctx *ctx, struct isl_coalesce_info *info, |
| 3536 | int start1, int end1, int start2, int end2) |
| 3537 | { |
| 3538 | int i, j; |
| 3539 | |
| 3540 | for (i = end1 - 1; i >= start1; --i) { |
| 3541 | if (info[i].removed) |
| 3542 | continue; |
| 3543 | for (j = isl_max(i + 1, start2); j < end2; ++j) { |
| 3544 | enum isl_change changed; |
| 3545 | |
| 3546 | if (info[j].removed) |
| 3547 | continue; |
| 3548 | if (info[i].removed) |
| 3549 | isl_die(ctx, isl_error_internal,do { isl_handle_error(ctx, isl_error_internal, "basic map unexpectedly removed" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn295388/tools/polly/lib/External/isl/isl_coalesce.c" , 3551); return -1; } while (0) |
| 3550 | "basic map unexpectedly removed",do { isl_handle_error(ctx, isl_error_internal, "basic map unexpectedly removed" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn295388/tools/polly/lib/External/isl/isl_coalesce.c" , 3551); return -1; } while (0) |
| 3551 | return -1)do { isl_handle_error(ctx, isl_error_internal, "basic map unexpectedly removed" , "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn295388/tools/polly/lib/External/isl/isl_coalesce.c" , 3551); return -1; } while (0); |
| 3552 | changed = coalesce_pair(i, j, info); |
| 3553 | switch (changed) { |
| 3554 | case isl_change_error: |
| 3555 | return -1; |
| 3556 | case isl_change_none: |
| 3557 | case isl_change_drop_second: |
| 3558 | continue; |
| 3559 | case isl_change_drop_first: |
| 3560 | j = end2; |
| 3561 | break; |
| 3562 | case isl_change_fuse: |
| 3563 | j = i; |
| 3564 | break; |
| 3565 | } |
| 3566 | } |
| 3567 | } |
| 3568 | |
| 3569 | return 0; |
| 3570 | } |
| 3571 | |
| 3572 | /* Pairwise coalesce the basic maps described by the "n" elements of "info". |
| 3573 | * |
| 3574 | * We consider groups of basic maps that live in the same apparent |
| 3575 | * affine hull and we first coalesce within such a group before we |
| 3576 | * coalesce the elements in the group with elements of previously |
| 3577 | * considered groups. If a fuse happens during the second phase, |
| 3578 | * then we also reconsider the elements within the group. |
| 3579 | */ |
| 3580 | static int coalesce(isl_ctx *ctx, int n, struct isl_coalesce_info *info) |
| 3581 | { |
| 3582 | int start, end; |
| 3583 | |
| 3584 | for (end = n; end > 0; end = start) { |
| 3585 | start = end - 1; |
| 3586 | while (start >= 1 && |
| 3587 | info[start - 1].hull_hash == info[start].hull_hash) |
| 3588 | start--; |
| 3589 | if (coalesce_range(ctx, info, start, end, start, end) < 0) |
| 3590 | return -1; |
| 3591 | if (coalesce_range(ctx, info, start, end, end, n) < 0) |
| 3592 | return -1; |
| 3593 | } |
| 3594 | |
| 3595 | return 0; |
| 3596 | } |
| 3597 | |
| 3598 | /* Update the basic maps in "map" based on the information in "info". |
| 3599 | * In particular, remove the basic maps that have been marked removed and |
| 3600 | * update the others based on the information in the corresponding tableau. |
| 3601 | * Since we detected implicit equalities without calling |
| 3602 | * isl_basic_map_gauss, we need to do it now. |
| 3603 | * Also call isl_basic_map_simplify if we may have lost the definition |
| 3604 | * of one or more integer divisions. |
| 3605 | */ |
| 3606 | static __isl_give isl_map *update_basic_maps(__isl_take isl_map *map, |
| 3607 | int n, struct isl_coalesce_info *info) |
| 3608 | { |
| 3609 | int i; |
| 3610 | |
| 3611 | if (!map) |
| 3612 | return NULL((void*)0); |
| 3613 | |
| 3614 | for (i = n - 1; i >= 0; --i) { |
| 3615 | if (info[i].removed) { |
| 3616 | isl_basic_map_free(map->p[i]); |
| 3617 | if (i != map->n - 1) |
| 3618 | map->p[i] = map->p[map->n - 1]; |
| 3619 | map->n--; |
| 3620 | continue; |
| 3621 | } |
| 3622 | |
| 3623 | info[i].bmap = isl_basic_map_update_from_tab(info[i].bmap, |
| 3624 | info[i].tab); |
| 3625 | info[i].bmap = isl_basic_map_gauss(info[i].bmap, NULL((void*)0)); |
| 3626 | if (info[i].simplify) |
| 3627 | info[i].bmap = isl_basic_map_simplify(info[i].bmap); |
| 3628 | info[i].bmap = isl_basic_map_finalize(info[i].bmap); |
| 3629 | if (!info[i].bmap) |
| 3630 | return isl_map_free(map); |
| 3631 | ISL_F_SET(info[i].bmap, ISL_BASIC_MAP_NO_IMPLICIT)(((info[i].bmap)->flags) |= ((1 << 2))); |
| 3632 | ISL_F_SET(info[i].bmap, ISL_BASIC_MAP_NO_REDUNDANT)(((info[i].bmap)->flags) |= ((1 << 3))); |
| 3633 | isl_basic_map_free(map->p[i]); |
| 3634 | map->p[i] = info[i].bmap; |
| 3635 | info[i].bmap = NULL((void*)0); |
| 3636 | } |
| 3637 | |
| 3638 | return map; |
| 3639 | } |
| 3640 | |
| 3641 | /* For each pair of basic maps in the map, check if the union of the two |
| 3642 | * can be represented by a single basic map. |
| 3643 | * If so, replace the pair by the single basic map and start over. |
| 3644 | * |
| 3645 | * We factor out any (hidden) common factor from the constraint |
| 3646 | * coefficients to improve the detection of adjacent constraints. |
| 3647 | * |
| 3648 | * Since we are constructing the tableaus of the basic maps anyway, |
| 3649 | * we exploit them to detect implicit equalities and redundant constraints. |
| 3650 | * This also helps the coalescing as it can ignore the redundant constraints. |
| 3651 | * In order to avoid confusion, we make all implicit equalities explicit |
| 3652 | * in the basic maps. We don't call isl_basic_map_gauss, though, |
| 3653 | * as that may affect the number of constraints. |
| 3654 | * This means that we have to call isl_basic_map_gauss at the end |
| 3655 | * of the computation (in update_basic_maps) to ensure that |
| 3656 | * the basic maps are not left in an unexpected state. |
| 3657 | * For each basic map, we also compute the hash of the apparent affine hull |
| 3658 | * for use in coalesce. |
| 3659 | */ |
| 3660 | struct isl_map *isl_map_coalesce(struct isl_map *map) |
| 3661 | { |
| 3662 | int i; |
| 3663 | unsigned n; |
| 3664 | isl_ctx *ctx; |
| 3665 | struct isl_coalesce_info *info = NULL((void*)0); |
| 3666 | |
| 3667 | map = isl_map_remove_empty_parts(map); |
| 3668 | if (!map) |
| 3669 | return NULL((void*)0); |
| 3670 | |
| 3671 | if (map->n <= 1) |
| 3672 | return map; |
| 3673 | |
| 3674 | ctx = isl_map_get_ctx(map); |
| 3675 | map = isl_map_sort_divs(map); |
| 3676 | map = isl_map_cow(map); |
| 3677 | |
| 3678 | if (!map) |
| 3679 | return NULL((void*)0); |
| 3680 | |
| 3681 | n = map->n; |
| 3682 | |
| 3683 | info = isl_calloc_array(map->ctx, struct isl_coalesce_info, n)((struct isl_coalesce_info *)isl_calloc_or_die(map->ctx, n , sizeof(struct isl_coalesce_info))); |
| 3684 | if (!info) |
| 3685 | goto error; |
| 3686 | |
| 3687 | for (i = 0; i < map->n; ++i) { |
| 3688 | map->p[i] = isl_basic_map_reduce_coefficients(map->p[i]); |
| 3689 | if (!map->p[i]) |
| 3690 | goto error; |
| 3691 | info[i].bmap = isl_basic_map_copy(map->p[i]); |
| 3692 | info[i].tab = isl_tab_from_basic_map(info[i].bmap, 0); |
| 3693 | if (!info[i].tab) |
| 3694 | goto error; |
| 3695 | if (!ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_NO_IMPLICIT)(!!(((info[i].bmap)->flags) & ((1 << 2))))) |
| 3696 | if (isl_tab_detect_implicit_equalities(info[i].tab) < 0) |
| 3697 | goto error; |
| 3698 | info[i].bmap = isl_tab_make_equalities_explicit(info[i].tab, |
| 3699 | info[i].bmap); |
| 3700 | if (!info[i].bmap) |
| 3701 | goto error; |
| 3702 | if (!ISL_F_ISSET(info[i].bmap, ISL_BASIC_MAP_NO_REDUNDANT)(!!(((info[i].bmap)->flags) & ((1 << 3))))) |
| 3703 | if (isl_tab_detect_redundant(info[i].tab) < 0) |
| 3704 | goto error; |
| 3705 | if (coalesce_info_set_hull_hash(&info[i]) < 0) |
| 3706 | goto error; |
| 3707 | } |
| 3708 | for (i = map->n - 1; i >= 0; --i) |
| 3709 | if (info[i].tab->empty) |
| 3710 | drop(&info[i]); |
| 3711 | |
| 3712 | if (coalesce(ctx, n, info) < 0) |
| 3713 | goto error; |
| 3714 | |
| 3715 | map = update_basic_maps(map, n, info); |
| 3716 | |
| 3717 | clear_coalesce_info(n, info); |
| 3718 | |
| 3719 | return map; |
| 3720 | error: |
| 3721 | clear_coalesce_info(n, info); |
| 3722 | isl_map_free(map); |
| 3723 | return NULL((void*)0); |
| 3724 | } |
| 3725 | |
| 3726 | /* For each pair of basic sets in the set, check if the union of the two |
| 3727 | * can be represented by a single basic set. |
| 3728 | * If so, replace the pair by the single basic set and start over. |
| 3729 | */ |
| 3730 | struct isl_setisl_map *isl_set_coalesce(struct isl_setisl_map *set) |
| 3731 | { |
| 3732 | return set_from_map(isl_map_coalesce(set_to_map(set))); |
| 3733 | } |