isl_morph.c

   1 /*
   2  * Copyright 2010-2011 INRIA Saclay
   3  * Copyright 2014      Ecole Normale Superieure
   4  *
   5  * Use of this software is governed by the MIT license
   6  *
   7  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   8  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   9  * 91893 Orsay, France
  10  * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
  11  */
  12
  13 #include <isl_map_private.h>
  14 #include <isl_aff_private.h>
  15 #include <isl_morph.h>
  16 #include <isl_seq.h>
  17 #include <isl_mat_private.h>
  18 #include <isl_space_private.h>
  19 #include <isl_equalities.h>
  20 #include <isl_id_private.h>
  21 #include <isl_aff_private.h>
  22 #include <isl_vec_private.h>
  23
  24 isl_ctx *isl_morph_get_ctx(__isl_keep isl_morph *morph)
  25 {
  26         if (!morph)
  27                 return NULL;
  28         return isl_basic_set_get_ctx(morph->dom);
  29 }
  30
  31 __isl_give isl_morph *isl_morph_alloc(
  32         __isl_take isl_basic_set *dom, __isl_take isl_basic_set *ran,
  33         __isl_take isl_mat *map, __isl_take isl_mat *inv)
  34 {
  35         isl_morph *morph;
  36
  37         if (!dom || !ran || !map || !inv)
  38                 goto error;
  39
  40         morph = isl_alloc_type(dom->ctx, struct isl_morph);
  41         if (!morph)
  42                 goto error;
  43
  44         morph->ref = 1;
  45         morph->dom = dom;
  46         morph->ran = ran;
  47         morph->map = map;
  48         morph->inv = inv;
  49
  50         return morph;
  51 error:
  52         isl_basic_set_free(dom);
  53         isl_basic_set_free(ran);
  54         isl_mat_free(map);
  55         isl_mat_free(inv);
  56         return NULL;
  57 }
  58
  59 __isl_give isl_morph *isl_morph_copy(__isl_keep isl_morph *morph)
  60 {
  61         if (!morph)
  62                 return NULL;
  63
  64         morph->ref++;
  65         return morph;
  66 }
  67
  68 __isl_give isl_morph *isl_morph_dup(__isl_keep isl_morph *morph)
  69 {
  70         if (!morph)
  71                 return NULL;
  72
  73         return isl_morph_alloc(isl_basic_set_copy(morph->dom),
  74                 isl_basic_set_copy(morph->ran),
  75                 isl_mat_copy(morph->map), isl_mat_copy(morph->inv));
  76 }
  77
  78 __isl_give isl_morph *isl_morph_cow(__isl_take isl_morph *morph)
  79 {
  80         if (!morph)
  81                 return NULL;
  82
  83         if (morph->ref == 1)
  84                 return morph;
  85         morph->ref--;
  86         return isl_morph_dup(morph);
  87 }
  88
  89 __isl_null isl_morph *isl_morph_free(__isl_take isl_morph *morph)
  90 {
  91         if (!morph)
  92                 return NULL;
  93
  94         if (--morph->ref > 0)
  95                 return NULL;
  96
  97         isl_basic_set_free(morph->dom);
  98         isl_basic_set_free(morph->ran);
  99         isl_mat_free(morph->map);
 100         isl_mat_free(morph->inv);
 101         free(morph);
 102
 103         return NULL;
 104 }
 105
 106 /* Is "morph" an identity on the parameters?
 107  */
 108 static isl_bool identity_on_parameters(__isl_keep isl_morph *morph)
 109 {
 110         isl_bool is_identity;
 111         isl_size nparam, nparam_ran;
 112         isl_mat *sub;
 113
 114         nparam = isl_morph_dom_dim(morph, isl_dim_param);
 115         nparam_ran = isl_morph_ran_dim(morph, isl_dim_param);
 116         if (nparam < 0 || nparam_ran < 0)
 117                 return isl_bool_error;
 118         if (nparam != nparam_ran)
 119                 return isl_bool_false;
 120         if (nparam == 0)
 121                 return isl_bool_true;
 122         sub = isl_mat_sub_alloc(morph->map, 0, 1 + nparam, 0, 1 + nparam);
 123         is_identity = isl_mat_is_scaled_identity(sub);
 124         isl_mat_free(sub);
 125
 126         return is_identity;
 127 }
 128
 129 /* Return an affine expression of the variables of the range of "morph"
 130  * in terms of the parameters and the variables of the domain on "morph".
 131  *
 132  * In order for the space manipulations to make sense, we require
 133  * that the parameters are not modified by "morph".
 134  */
 135 __isl_give isl_multi_aff *isl_morph_get_var_multi_aff(
 136         __isl_keep isl_morph *morph)
 137 {
 138         isl_space *dom, *ran, *space;
 139         isl_local_space *ls;
 140         isl_multi_aff *ma;
 141         isl_size nparam, nvar;
 142         int i;
 143         isl_bool is_identity;
 144
 145         if (!morph)
 146                 return NULL;
 147
 148         is_identity = identity_on_parameters(morph);
 149         if (is_identity < 0)
 150                 return NULL;
 151         if (!is_identity)
 152                 isl_die(isl_morph_get_ctx(morph), isl_error_invalid,
 153                         "cannot handle parameter compression", return NULL);
 154
 155         dom = isl_morph_get_dom_space(morph);
 156         ls = isl_local_space_from_space(isl_space_copy(dom));
 157         ran = isl_morph_get_ran_space(morph);
 158         space = isl_space_map_from_domain_and_range(dom, ran);
 159         ma = isl_multi_aff_zero(space);
 160
 161         nparam = isl_multi_aff_dim(ma, isl_dim_param);
 162         nvar = isl_multi_aff_dim(ma, isl_dim_out);
 163         if (nparam < 0 || nvar < 0)
 164                 ma = isl_multi_aff_free(ma);
 165         for (i = 0; i < nvar; ++i) {
 166                 isl_val *val;
 167                 isl_vec *v;
 168                 isl_aff *aff;
 169
 170                 v = isl_mat_get_row(morph->map, 1 + nparam + i);
 171                 v = isl_vec_insert_els(v, 0, 1);
 172                 val = isl_mat_get_element_val(morph->map, 0, 0);
 173                 v = isl_vec_set_element_val(v, 0, val);
 174                 aff = isl_aff_alloc_vec(isl_local_space_copy(ls), v);
 175                 ma = isl_multi_aff_set_aff(ma, i, aff);
 176         }
 177
 178         isl_local_space_free(ls);
 179         return ma;
 180 }
 181
 182 /* Return the domain space of "morph".
 183  */
 184 static __isl_keep isl_space *isl_morph_peek_dom_space(
 185         __isl_keep isl_morph *morph)
 186 {
 187         if (!morph)
 188                 return NULL;
 189
 190         return isl_basic_set_peek_space(morph->dom);
 191 }
 192
 193 /* Return a copy of the domain space of "morph".
 194  */
 195 __isl_give isl_space *isl_morph_get_dom_space(__isl_keep isl_morph *morph)
 196 {
 197         return isl_space_copy(isl_morph_peek_dom_space(morph));
 198 }
 199
 200 /* Check that the match against "space" with result "match" was successful.
 201  */
 202 static isl_stat check_space_match(__isl_keep isl_space *space, isl_bool match)
 203 {
 204         if (match < 0)
 205                 return isl_stat_error;
 206         if (!match)
 207                 isl_die(isl_space_get_ctx(space), isl_error_invalid,
 208                         "spaces don't match", return isl_stat_error);
 209
 210         return isl_stat_ok;
 211 }
 212
 213 /* Check that "morph" can be applied to the "space".
 214  */
 215 isl_stat isl_morph_check_applies(__isl_keep isl_morph *morph,
 216         __isl_keep isl_space *space)
 217 {
 218         isl_space *dom_space;
 219         isl_bool applies;
 220
 221         dom_space = isl_morph_peek_dom_space(morph);
 222         applies = isl_space_is_equal(dom_space, space);
 223         return check_space_match(space, applies);
 224 }
 225
 226 __isl_give isl_space *isl_morph_get_ran_space(__isl_keep isl_morph *morph)
 227 {
 228         if (!morph)
 229                 return NULL;
 230
 231         return isl_space_copy(morph->ran->dim);
 232 }
 233
 234 isl_size isl_morph_dom_dim(__isl_keep isl_morph *morph, enum isl_dim_type type)
 235 {
 236         if (!morph)
 237                 return isl_size_error;
 238
 239         return isl_basic_set_dim(morph->dom, type);
 240 }
 241
 242 isl_size isl_morph_ran_dim(__isl_keep isl_morph *morph, enum isl_dim_type type)
 243 {
 244         if (!morph)
 245                 return isl_size_error;
 246
 247         return isl_basic_set_dim(morph->ran, type);
 248 }
 249
 250 __isl_give isl_morph *isl_morph_remove_dom_dims(__isl_take isl_morph *morph,
 251         enum isl_dim_type type, unsigned first, unsigned n)
 252 {
 253         isl_size dom_offset;
 254
 255         if (n == 0)
 256                 return morph;
 257
 258         morph = isl_morph_cow(morph);
 259         if (!morph)
 260                 return NULL;
 261
 262         dom_offset = isl_space_offset(morph->dom->dim, type);
 263         if (dom_offset < 0)
 264                 return isl_morph_free(morph);
 265
 266         morph->dom = isl_basic_set_remove_dims(morph->dom, type, first, n);
 267
 268         morph->map = isl_mat_drop_cols(morph->map, 1 + dom_offset + first, n);
 269
 270         morph->inv = isl_mat_drop_rows(morph->inv, 1 + dom_offset + first, n);
 271
 272         if (morph->dom && morph->ran && morph->map && morph->inv)
 273                 return morph;
 274
 275         isl_morph_free(morph);
 276         return NULL;
 277 }
 278
 279 __isl_give isl_morph *isl_morph_remove_ran_dims(__isl_take isl_morph *morph,
 280         enum isl_dim_type type, unsigned first, unsigned n)
 281 {
 282         isl_size ran_offset;
 283
 284         if (n == 0)
 285                 return morph;
 286
 287         morph = isl_morph_cow(morph);
 288         if (!morph)
 289                 return NULL;
 290
 291         ran_offset = isl_space_offset(morph->ran->dim, type);
 292         if (ran_offset < 0)
 293                 return isl_morph_free(morph);
 294
 295         morph->ran = isl_basic_set_remove_dims(morph->ran, type, first, n);
 296
 297         morph->map = isl_mat_drop_rows(morph->map, 1 + ran_offset + first, n);
 298
 299         morph->inv = isl_mat_drop_cols(morph->inv, 1 + ran_offset + first, n);
 300
 301         if (morph->dom && morph->ran && morph->map && morph->inv)
 302                 return morph;
 303
 304         isl_morph_free(morph);
 305         return NULL;
 306 }
 307
 308 /* Project domain of morph onto its parameter domain.
 309  */
 310 __isl_give isl_morph *isl_morph_dom_params(__isl_take isl_morph *morph)
 311 {
 312         isl_size n;
 313
 314         morph = isl_morph_cow(morph);
 315         if (!morph)
 316                 return NULL;
 317         n = isl_basic_set_dim(morph->dom, isl_dim_set);
 318         if (n < 0)
 319                 return isl_morph_free(morph);
 320         morph = isl_morph_remove_dom_dims(morph, isl_dim_set, 0, n);
 321         if (!morph)
 322                 return NULL;
 323         morph->dom = isl_basic_set_params(morph->dom);
 324         if (morph->dom)
 325                 return morph;
 326
 327         isl_morph_free(morph);
 328         return NULL;
 329 }
 330
 331 /* Project range of morph onto its parameter domain.
 332  */
 333 __isl_give isl_morph *isl_morph_ran_params(__isl_take isl_morph *morph)
 334 {
 335         isl_size n;
 336
 337         morph = isl_morph_cow(morph);
 338         if (!morph)
 339                 return NULL;
 340         n = isl_basic_set_dim(morph->ran, isl_dim_set);
 341         if (n < 0)
 342                 return isl_morph_free(morph);
 343         morph = isl_morph_remove_ran_dims(morph, isl_dim_set, 0, n);
 344         if (!morph)
 345                 return NULL;
 346         morph->ran = isl_basic_set_params(morph->ran);
 347         if (morph->ran)
 348                 return morph;
 349
 350         isl_morph_free(morph);
 351         return NULL;
 352 }
 353
 354 /* Replace the identifier of the tuple of the range of the morph by "id".
 355  */
 356 static __isl_give isl_morph *isl_morph_set_ran_tuple_id(
 357         __isl_take isl_morph *morph, __isl_keep isl_id *id)
 358 {
 359         morph = isl_morph_cow(morph);
 360         if (!morph)
 361                 return NULL;
 362         morph->ran = isl_basic_set_set_tuple_id(morph->ran, isl_id_copy(id));
 363         if (!morph->ran)
 364                 return isl_morph_free(morph);
 365         return morph;
 366 }
 367
 368 void isl_morph_print_internal(__isl_take isl_morph *morph, FILE *out)
 369 {
 370         if (!morph)
 371                 return;
 372
 373         isl_basic_set_dump(morph->dom);
 374         isl_basic_set_dump(morph->ran);
 375         isl_mat_print_internal(morph->map, out, 4);
 376         isl_mat_print_internal(morph->inv, out, 4);
 377 }
 378
 379 void isl_morph_dump(__isl_take isl_morph *morph)
 380 {
 381         isl_morph_print_internal(morph, stderr);
 382 }
 383
 384 __isl_give isl_morph *isl_morph_identity(__isl_keep isl_basic_set *bset)
 385 {
 386         isl_mat *id;
 387         isl_basic_set *universe;
 388         isl_size total;
 389
 390         total = isl_basic_set_dim(bset, isl_dim_all);
 391         if (total < 0)
 392                 return NULL;
 393
 394         id = isl_mat_identity(bset->ctx, 1 + total);
 395         universe = isl_basic_set_universe(isl_space_copy(bset->dim));
 396
 397         return isl_morph_alloc(universe, isl_basic_set_copy(universe),
 398                 id, isl_mat_copy(id));
 399 }
 400
 401 /* Create a(n identity) morphism between empty sets of the same dimension
 402  * a "bset".
 403  */
 404 __isl_give isl_morph *isl_morph_empty(__isl_keep isl_basic_set *bset)
 405 {
 406         isl_mat *id;
 407         isl_basic_set *empty;
 408         isl_size total;
 409
 410         total = isl_basic_set_dim(bset, isl_dim_all);
 411         if (total < 0)
 412                 return NULL;
 413
 414         id = isl_mat_identity(bset->ctx, 1 + total);
 415         empty = isl_basic_set_empty(isl_space_copy(bset->dim));
 416
 417         return isl_morph_alloc(empty, isl_basic_set_copy(empty),
 418                 id, isl_mat_copy(id));
 419 }
 420
 421 /* Construct a basic set described by the "n" equalities of "bset" starting
 422  * at "first".
 423  */
 424 static __isl_give isl_basic_set *copy_equalities(__isl_keep isl_basic_set *bset,
 425         unsigned first, unsigned n)
 426 {
 427         int i, k;
 428         isl_basic_set *eq;
 429         isl_size total;
 430
 431         total = isl_basic_set_dim(bset, isl_dim_all);
 432         if (total < 0 || isl_basic_set_check_no_locals(bset) < 0)
 433                 return NULL;
 434
 435         eq = isl_basic_set_alloc_space(isl_basic_set_get_space(bset), 0, n, 0);
 436         if (!eq)
 437                 return NULL;
 438         for (i = 0; i < n; ++i) {
 439                 k = isl_basic_set_alloc_equality(eq);
 440                 if (k < 0)
 441                         goto error;
 442                 isl_seq_cpy(eq->eq[k], bset->eq[first + i], 1 + total);
 443         }
 444
 445         return eq;
 446 error:
 447         isl_basic_set_free(eq);
 448         return NULL;
 449 }
 450
 451 /* Given a basic set, exploit the equalities in the basic set to construct
 452  * a morphism that maps the basic set to a lower-dimensional space.
 453  * Specifically, the morphism reduces the number of dimensions of type "type".
 454  *
 455  * We first select the equalities of interest, that is those that involve
 456  * variables of type "type" and no later variables.
 457  * Denote those equalities as
 458  *
 459  *              -C(p) + M x = 0
 460  *
 461  * where C(p) depends on the parameters if type == isl_dim_set and
 462  * is a constant if type == isl_dim_param.
 463  *
 464  * Use isl_mat_final_variable_compression to construct a compression
 465  *
 466  *      x = T x'
 467  *
 468  *      x' = Q x
 469  *
 470  * If T is a zero-column matrix, then the set of equality constraints
 471  * do not admit a solution.  In this case, an empty morphism is returned.
 472  *
 473  * Both matrices are extended to map the full original space to the full
 474  * compressed space.
 475  */
 476 __isl_give isl_morph *isl_basic_set_variable_compression(
 477         __isl_keep isl_basic_set *bset, enum isl_dim_type type)
 478 {
 479         unsigned otype;
 480         isl_size ntype;
 481         unsigned orest;
 482         unsigned nrest;
 483         isl_size total;
 484         int f_eq, n_eq;
 485         isl_space *space;
 486         isl_mat *E, *Q, *C;
 487         isl_basic_set *dom, *ran;
 488
 489         if (!bset)
 490                 return NULL;
 491
 492         if (isl_basic_set_plain_is_empty(bset))
 493                 return isl_morph_empty(bset);
 494
 495         if (isl_basic_set_check_no_locals(bset) < 0)
 496                 return NULL;
 497
 498         ntype = isl_basic_set_dim(bset, type);
 499         total = isl_basic_set_dim(bset, isl_dim_all);
 500         if (ntype < 0 || total < 0)
 501                 return NULL;
 502         otype = isl_basic_set_offset(bset, type);
 503         orest = otype + ntype;
 504         nrest = total - (orest - 1);
 505
 506         for (f_eq = 0; f_eq < bset->n_eq; ++f_eq)
 507                 if (isl_seq_first_non_zero(bset->eq[f_eq] + orest, nrest) == -1)
 508                         break;
 509         for (n_eq = 0; f_eq + n_eq < bset->n_eq; ++n_eq)
 510                 if (isl_seq_first_non_zero(bset->eq[f_eq + n_eq] + otype, ntype) == -1)
 511                         break;
 512         if (n_eq == 0)
 513                 return isl_morph_identity(bset);
 514
 515         E = isl_mat_sub_alloc6(bset->ctx, bset->eq, f_eq, n_eq, 0, orest);
 516         C = isl_mat_final_variable_compression(E, otype - 1, &Q);
 517         if (!Q)
 518                 C = isl_mat_free(C);
 519         if (C && C->n_col == 0) {
 520                 isl_mat_free(C);
 521                 isl_mat_free(Q);
 522                 return isl_morph_empty(bset);
 523         }
 524
 525         Q = isl_mat_diagonal(Q, isl_mat_identity(bset->ctx, nrest));
 526         C = isl_mat_diagonal(C, isl_mat_identity(bset->ctx, nrest));
 527
 528         space = isl_space_copy(bset->dim);
 529         space = isl_space_drop_dims(space, type, 0, ntype);
 530         space = isl_space_add_dims(space, type, ntype - n_eq);
 531         ran = isl_basic_set_universe(space);
 532         dom = copy_equalities(bset, f_eq, n_eq);
 533
 534         return isl_morph_alloc(dom, ran, Q, C);
 535 }
 536
 537 /* Given a basic set, exploit the equalities in the basic set to construct
 538  * a morphism that maps the basic set to a lower-dimensional space
 539  * with identifier "id".
 540  * Specifically, the morphism reduces the number of set dimensions.
 541  */
 542 __isl_give isl_morph *isl_basic_set_variable_compression_with_id(
 543         __isl_keep isl_basic_set *bset, __isl_keep isl_id *id)
 544 {
 545         isl_morph *morph;
 546
 547         morph = isl_basic_set_variable_compression(bset, isl_dim_set);
 548         morph = isl_morph_set_ran_tuple_id(morph, id);
 549         return morph;
 550 }
 551
 552 /* Construct a parameter compression for "bset".
 553  * We basically just call isl_mat_parameter_compression with the right input
 554  * and then extend the resulting matrix to include the variables.
 555  *
 556  * The implementation assumes that "bset" does not have any equalities
 557  * that only involve the parameters and that isl_basic_set_gauss has
 558  * been applied to "bset".
 559  *
 560  * Let the equalities be given as
 561  *
 562  *      B(p) + A x = 0.
 563  *
 564  * We use isl_mat_parameter_compression_ext to compute the compression
 565  *
 566  *      p = T p'.
 567  */
 568 __isl_give isl_morph *isl_basic_set_parameter_compression(
 569         __isl_keep isl_basic_set *bset)
 570 {
 571         isl_size nparam;
 572         isl_size nvar;
 573         isl_size n_div;
 574         int n_eq;
 575         isl_mat *H, *B;
 576         isl_mat *map, *inv;
 577         isl_basic_set *dom, *ran;
 578
 579         if (!bset)
 580                 return NULL;
 581
 582         if (isl_basic_set_plain_is_empty(bset))
 583                 return isl_morph_empty(bset);
 584         if (bset->n_eq == 0)
 585                 return isl_morph_identity(bset);
 586
 587         n_eq = bset->n_eq;
 588         nparam = isl_basic_set_dim(bset, isl_dim_param);
 589         nvar = isl_basic_set_dim(bset, isl_dim_set);
 590         n_div = isl_basic_set_dim(bset, isl_dim_div);
 591         if (nparam < 0 || nvar < 0 || n_div < 0)
 592                 return NULL;
 593
 594         if (isl_seq_first_non_zero(bset->eq[bset->n_eq - 1] + 1 + nparam,
 595                                     nvar + n_div) == -1)
 596                 isl_die(isl_basic_set_get_ctx(bset), isl_error_invalid,
 597                         "input not allowed to have parameter equalities",
 598                         return NULL);
 599         if (n_eq > nvar + n_div)
 600                 isl_die(isl_basic_set_get_ctx(bset), isl_error_invalid,
 601                         "input not gaussed", return NULL);
 602
 603         B = isl_mat_sub_alloc6(bset->ctx, bset->eq, 0, n_eq, 0, 1 + nparam);
 604         H = isl_mat_sub_alloc6(bset->ctx, bset->eq,
 605                                 0, n_eq, 1 + nparam, nvar + n_div);
 606         inv = isl_mat_parameter_compression_ext(B, H);
 607         inv = isl_mat_diagonal(inv, isl_mat_identity(bset->ctx, nvar));
 608         map = isl_mat_right_inverse(isl_mat_copy(inv));
 609
 610         dom = isl_basic_set_universe(isl_space_copy(bset->dim));
 611         ran = isl_basic_set_universe(isl_space_copy(bset->dim));
 612
 613         return isl_morph_alloc(dom, ran, map, inv);
 614 }
 615
 616 /* Construct an isl_multi_aff that corresponds
 617  * to the affine transformation matrix "mat" and
 618  * that lives in an anonymous space.
 619  */
 620 static __isl_give isl_multi_aff *isl_multi_aff_from_aff_mat_anonymous(
 621         __isl_take isl_mat *mat)
 622 {
 623         isl_size n_row, n_col;
 624         isl_ctx *ctx;
 625         isl_space *space;
 626
 627         ctx = isl_mat_get_ctx(mat);
 628         n_row = isl_mat_rows(mat);
 629         n_col = isl_mat_cols(mat);
 630         if (n_row < 0 || n_col < 0)
 631                 space = NULL;
 632         else
 633                 space = isl_space_alloc(ctx, 0, n_col - 1, n_row - 1);
 634
 635         return isl_multi_aff_from_aff_mat(space, mat);
 636 }
 637
 638 /* Apply the morphism to the basic set.
 639  * In particular, compute the preimage of "bset" under the inverse mapping
 640  * in morph and intersect with the range of the morphism.
 641  * Note that the mapping in morph applies to both parameters and set dimensions,
 642  * so the parameters need to be treated as set dimensions during the call
 643  * to isl_basic_set_preimage_multi_aff.
 644  */
 645 __isl_give isl_basic_set *isl_morph_basic_set(__isl_take isl_morph *morph,
 646         __isl_take isl_basic_set *bset)
 647 {
 648         isl_size n_param;
 649         isl_space *space;
 650         isl_multi_aff *ma;
 651
 652         if (!morph || isl_basic_set_check_equal_space(bset, morph->dom) < 0)
 653                 goto error;
 654         n_param = isl_basic_set_dim(morph->dom, isl_dim_param);
 655         if (n_param < 0)
 656                 goto error;
 657
 658         ma = isl_multi_aff_from_aff_mat_anonymous(isl_mat_copy(morph->inv));
 659
 660         bset = isl_basic_set_move_dims(bset, isl_dim_set, 0,
 661                                         isl_dim_param, 0, n_param);
 662         bset = isl_basic_set_preimage_multi_aff(bset, ma);
 663         space = isl_basic_set_get_space(morph->ran);
 664         bset = isl_basic_set_reset_space(bset, space);
 665         bset = isl_basic_set_intersect(bset, isl_basic_set_copy(morph->ran));
 666
 667         isl_morph_free(morph);
 668         return bset;
 669 error:
 670         isl_morph_free(morph);
 671         isl_basic_set_free(bset);
 672         return NULL;
 673 }
 674
 675 /* Apply the morphism to the set.
 676  * In particular, compute the preimage of "set" under the inverse mapping
 677  * in morph and intersect with the range of the morphism.
 678  * Note that the mapping in morph applies to both parameters and set dimensions,
 679  * so the parameters need to be treated as set dimensions during the call
 680  * to isl_set_preimage_multi_aff.
 681  */
 682 __isl_give isl_set *isl_morph_set(__isl_take isl_morph *morph,
 683         __isl_take isl_set *set)
 684 {
 685         isl_size n_param;
 686         isl_space *space;
 687         isl_multi_aff *ma;
 688         isl_basic_set *ran;
 689
 690         if (!morph || isl_set_basic_set_check_equal_space(set, morph->dom) < 0)
 691                 goto error;
 692         n_param = isl_basic_set_dim(morph->dom, isl_dim_param);
 693         if (n_param < 0)
 694                 goto error;
 695
 696         ma = isl_multi_aff_from_aff_mat_anonymous(isl_mat_copy(morph->inv));
 697
 698         set = isl_set_move_dims(set, isl_dim_set, 0, isl_dim_param, 0, n_param);
 699         set = isl_set_preimage_multi_aff(set, ma);
 700         space = isl_basic_set_get_space(morph->ran);
 701         set = isl_set_reset_space(set, space);
 702         ran = isl_basic_set_copy(morph->ran);
 703         set = isl_set_intersect(set, isl_set_from_basic_set(ran));
 704
 705         isl_morph_free(morph);
 706         return set;
 707 error:
 708         isl_set_free(set);
 709         isl_morph_free(morph);
 710         return NULL;
 711 }
 712
 713 /* Construct a morphism that first does morph2 and then morph1.
 714  */
 715 __isl_give isl_morph *isl_morph_compose(__isl_take isl_morph *morph1,
 716         __isl_take isl_morph *morph2)
 717 {
 718         isl_mat *map, *inv;
 719         isl_basic_set *dom, *ran;
 720
 721         if (!morph1 || !morph2)
 722                 goto error;
 723
 724         map = isl_mat_product(isl_mat_copy(morph1->map), isl_mat_copy(morph2->map));
 725         inv = isl_mat_product(isl_mat_copy(morph2->inv), isl_mat_copy(morph1->inv));
 726         dom = isl_morph_basic_set(isl_morph_inverse(isl_morph_copy(morph2)),
 727                                   isl_basic_set_copy(morph1->dom));
 728         dom = isl_basic_set_intersect(dom, isl_basic_set_copy(morph2->dom));
 729         ran = isl_morph_basic_set(isl_morph_copy(morph1),
 730                                   isl_basic_set_copy(morph2->ran));
 731         ran = isl_basic_set_intersect(ran, isl_basic_set_copy(morph1->ran));
 732
 733         isl_morph_free(morph1);
 734         isl_morph_free(morph2);
 735
 736         return isl_morph_alloc(dom, ran, map, inv);
 737 error:
 738         isl_morph_free(morph1);
 739         isl_morph_free(morph2);
 740         return NULL;
 741 }
 742
 743 __isl_give isl_morph *isl_morph_inverse(__isl_take isl_morph *morph)
 744 {
 745         isl_basic_set *bset;
 746         isl_mat *mat;
 747
 748         morph = isl_morph_cow(morph);
 749         if (!morph)
 750                 return NULL;
 751
 752         bset = morph->dom;
 753         morph->dom = morph->ran;
 754         morph->ran = bset;
 755
 756         mat = morph->map;
 757         morph->map = morph->inv;
 758         morph->inv = mat;
 759
 760         return morph;
 761 }
 762
 763 /* We detect all the equalities first to avoid implicit equalities
 764  * being discovered during the computations.  In particular,
 765  * the compression on the variables could expose additional stride
 766  * constraints on the parameters.  This would result in existentially
 767  * quantified variables after applying the resulting morph, which
 768  * in turn could break invariants of the calling functions.
 769  */
 770 __isl_give isl_morph *isl_basic_set_full_compression(
 771         __isl_keep isl_basic_set *bset)
 772 {
 773         isl_morph *morph, *morph2;
 774
 775         bset = isl_basic_set_copy(bset);
 776         bset = isl_basic_set_detect_equalities(bset);
 777
 778         morph = isl_basic_set_variable_compression(bset, isl_dim_param);
 779         bset = isl_morph_basic_set(isl_morph_copy(morph), bset);
 780
 781         morph2 = isl_basic_set_parameter_compression(bset);
 782         bset = isl_morph_basic_set(isl_morph_copy(morph2), bset);
 783
 784         morph = isl_morph_compose(morph2, morph);
 785
 786         morph2 = isl_basic_set_variable_compression(bset, isl_dim_set);
 787         isl_basic_set_free(bset);
 788
 789         morph = isl_morph_compose(morph2, morph);
 790
 791         return morph;
 792 }
 793
 794 __isl_give isl_vec *isl_morph_vec(__isl_take isl_morph *morph,
 795         __isl_take isl_vec *vec)
 796 {
 797         if (!morph)
 798                 goto error;
 799
 800         vec = isl_mat_vec_product(isl_mat_copy(morph->map), vec);
 801
 802         isl_morph_free(morph);
 803         return vec;
 804 error:
 805         isl_morph_free(morph);
 806         isl_vec_free(vec);
 807         return NULL;
 808 }