isl_aff.c

   1 /*
   2  * Copyright 2011      INRIA Saclay
   3  * Copyright 2011      Sven Verdoolaege
   4  * Copyright 2012      Ecole Normale Superieure
   5  *
   6  * Use of this software is governed by the GNU LGPLv2.1 license
   7  *
   8  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   9  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
  10  * 91893 Orsay, France
  11  * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
  12  */
  13
  14 #include <isl_ctx_private.h>
  15 #define ISL_DIM_H
  16 #include <isl_map_private.h>
  17 #include <isl_union_map_private.h>
  18 #include <isl_aff_private.h>
  19 #include <isl_space_private.h>
  20 #include <isl_local_space_private.h>
  21 #include <isl_mat_private.h>
  22 #include <isl_list_private.h>
  23 #include <isl/constraint.h>
  24 #include <isl/seq.h>
  25 #include <isl/set.h>
  26 #include <isl_config.h>
  27
  28 __isl_give isl_aff *isl_aff_alloc_vec(__isl_take isl_local_space *ls,
  29         __isl_take isl_vec *v)
  30 {
  31         isl_aff *aff;
  32
  33         if (!ls || !v)
  34                 goto error;
  35
  36         aff = isl_calloc_type(v->ctx, struct isl_aff);
  37         if (!aff)
  38                 goto error;
  39
  40         aff->ref = 1;
  41         aff->ls = ls;
  42         aff->v = v;
  43
  44         return aff;
  45 error:
  46         isl_local_space_free(ls);
  47         isl_vec_free(v);
  48         return NULL;
  49 }
  50
  51 __isl_give isl_aff *isl_aff_alloc(__isl_take isl_local_space *ls)
  52 {
  53         isl_ctx *ctx;
  54         isl_vec *v;
  55         unsigned total;
  56
  57         if (!ls)
  58                 return NULL;
  59
  60         ctx = isl_local_space_get_ctx(ls);
  61         if (!isl_local_space_divs_known(ls))
  62                 isl_die(ctx, isl_error_invalid, "local space has unknown divs",
  63                         goto error);
  64         if (!isl_local_space_is_set(ls))
  65                 isl_die(ctx, isl_error_invalid,
  66                         "domain of affine expression should be a set",
  67                         goto error);
  68
  69         total = isl_local_space_dim(ls, isl_dim_all);
  70         v = isl_vec_alloc(ctx, 1 + 1 + total);
  71         return isl_aff_alloc_vec(ls, v);
  72 error:
  73         isl_local_space_free(ls);
  74         return NULL;
  75 }
  76
  77 __isl_give isl_aff *isl_aff_zero_on_domain(__isl_take isl_local_space *ls)
  78 {
  79         isl_aff *aff;
  80
  81         aff = isl_aff_alloc(ls);
  82         if (!aff)
  83                 return NULL;
  84
  85         isl_int_set_si(aff->v->el[0], 1);
  86         isl_seq_clr(aff->v->el + 1, aff->v->size - 1);
  87
  88         return aff;
  89 }
  90
  91 __isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff)
  92 {
  93         if (!aff)
  94                 return NULL;
  95
  96         aff->ref++;
  97         return aff;
  98 }
  99
 100 __isl_give isl_aff *isl_aff_dup(__isl_keep isl_aff *aff)
 101 {
 102         if (!aff)
 103                 return NULL;
 104
 105         return isl_aff_alloc_vec(isl_local_space_copy(aff->ls),
 106                                  isl_vec_copy(aff->v));
 107 }
 108
 109 __isl_give isl_aff *isl_aff_cow(__isl_take isl_aff *aff)
 110 {
 111         if (!aff)
 112                 return NULL;
 113
 114         if (aff->ref == 1)
 115                 return aff;
 116         aff->ref--;
 117         return isl_aff_dup(aff);
 118 }
 119
 120 void *isl_aff_free(__isl_take isl_aff *aff)
 121 {
 122         if (!aff)
 123                 return NULL;
 124
 125         if (--aff->ref > 0)
 126                 return NULL;
 127
 128         isl_local_space_free(aff->ls);
 129         isl_vec_free(aff->v);
 130
 131         free(aff);
 132
 133         return NULL;
 134 }
 135
 136 isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff)
 137 {
 138         return aff ? isl_local_space_get_ctx(aff->ls) : NULL;
 139 }
 140
 141 /* Externally, an isl_aff has a map space, but internally, the
 142  * ls field corresponds to the domain of that space.
 143  */
 144 int isl_aff_dim(__isl_keep isl_aff *aff, enum isl_dim_type type)
 145 {
 146         if (!aff)
 147                 return 0;
 148         if (type == isl_dim_out)
 149                 return 1;
 150         if (type == isl_dim_in)
 151                 type = isl_dim_set;
 152         return isl_local_space_dim(aff->ls, type);
 153 }
 154
 155 __isl_give isl_space *isl_aff_get_domain_space(__isl_keep isl_aff *aff)
 156 {
 157         return aff ? isl_local_space_get_space(aff->ls) : NULL;
 158 }
 159
 160 __isl_give isl_space *isl_aff_get_space(__isl_keep isl_aff *aff)
 161 {
 162         isl_space *space;
 163         if (!aff)
 164                 return NULL;
 165         space = isl_local_space_get_space(aff->ls);
 166         space = isl_space_from_domain(space);
 167         space = isl_space_add_dims(space, isl_dim_out, 1);
 168         return space;
 169 }
 170
 171 __isl_give isl_local_space *isl_aff_get_domain_local_space(
 172         __isl_keep isl_aff *aff)
 173 {
 174         return aff ? isl_local_space_copy(aff->ls) : NULL;
 175 }
 176
 177 __isl_give isl_local_space *isl_aff_get_local_space(__isl_keep isl_aff *aff)
 178 {
 179         isl_local_space *ls;
 180         if (!aff)
 181                 return NULL;
 182         ls = isl_local_space_copy(aff->ls);
 183         ls = isl_local_space_from_domain(ls);
 184         ls = isl_local_space_add_dims(ls, isl_dim_out, 1);
 185         return ls;
 186 }
 187
 188 /* Externally, an isl_aff has a map space, but internally, the
 189  * ls field corresponds to the domain of that space.
 190  */
 191 const char *isl_aff_get_dim_name(__isl_keep isl_aff *aff,
 192         enum isl_dim_type type, unsigned pos)
 193 {
 194         if (!aff)
 195                 return NULL;
 196         if (type == isl_dim_out)
 197                 return NULL;
 198         if (type == isl_dim_in)
 199                 type = isl_dim_set;
 200         return isl_local_space_get_dim_name(aff->ls, type, pos);
 201 }
 202
 203 __isl_give isl_aff *isl_aff_reset_domain_space(__isl_take isl_aff *aff,
 204         __isl_take isl_space *dim)
 205 {
 206         aff = isl_aff_cow(aff);
 207         if (!aff || !dim)
 208                 goto error;
 209
 210         aff->ls = isl_local_space_reset_space(aff->ls, dim);
 211         if (!aff->ls)
 212                 return isl_aff_free(aff);
 213
 214         return aff;
 215 error:
 216         isl_aff_free(aff);
 217         isl_space_free(dim);
 218         return NULL;
 219 }
 220
 221 /* Reset the space of "aff".  This function is called from isl_pw_templ.c
 222  * and doesn't know if the space of an element object is represented
 223  * directly or through its domain.  It therefore passes along both.
 224  */
 225 __isl_give isl_aff *isl_aff_reset_space_and_domain(__isl_take isl_aff *aff,
 226         __isl_take isl_space *space, __isl_take isl_space *domain)
 227 {
 228         isl_space_free(space);
 229         return isl_aff_reset_domain_space(aff, domain);
 230 }
 231
 232 /* Reorder the coefficients of the affine expression based
 233  * on the given reodering.
 234  * The reordering r is assumed to have been extended with the local
 235  * variables.
 236  */
 237 static __isl_give isl_vec *vec_reorder(__isl_take isl_vec *vec,
 238         __isl_take isl_reordering *r, int n_div)
 239 {
 240         isl_vec *res;
 241         int i;
 242
 243         if (!vec || !r)
 244                 goto error;
 245
 246         res = isl_vec_alloc(vec->ctx,
 247                             2 + isl_space_dim(r->dim, isl_dim_all) + n_div);
 248         isl_seq_cpy(res->el, vec->el, 2);
 249         isl_seq_clr(res->el + 2, res->size - 2);
 250         for (i = 0; i < r->len; ++i)
 251                 isl_int_set(res->el[2 + r->pos[i]], vec->el[2 + i]);
 252
 253         isl_reordering_free(r);
 254         isl_vec_free(vec);
 255         return res;
 256 error:
 257         isl_vec_free(vec);
 258         isl_reordering_free(r);
 259         return NULL;
 260 }
 261
 262 /* Reorder the dimensions of the domain of "aff" according
 263  * to the given reordering.
 264  */
 265 __isl_give isl_aff *isl_aff_realign_domain(__isl_take isl_aff *aff,
 266         __isl_take isl_reordering *r)
 267 {
 268         aff = isl_aff_cow(aff);
 269         if (!aff)
 270                 goto error;
 271
 272         r = isl_reordering_extend(r, aff->ls->div->n_row);
 273         aff->v = vec_reorder(aff->v, isl_reordering_copy(r),
 274                                 aff->ls->div->n_row);
 275         aff->ls = isl_local_space_realign(aff->ls, r);
 276
 277         if (!aff->v || !aff->ls)
 278                 return isl_aff_free(aff);
 279
 280         return aff;
 281 error:
 282         isl_aff_free(aff);
 283         isl_reordering_free(r);
 284         return NULL;
 285 }
 286
 287 __isl_give isl_aff *isl_aff_align_params(__isl_take isl_aff *aff,
 288         __isl_take isl_space *model)
 289 {
 290         if (!aff || !model)
 291                 goto error;
 292
 293         if (!isl_space_match(aff->ls->dim, isl_dim_param,
 294                              model, isl_dim_param)) {
 295                 isl_reordering *exp;
 296
 297                 model = isl_space_drop_dims(model, isl_dim_in,
 298                                         0, isl_space_dim(model, isl_dim_in));
 299                 model = isl_space_drop_dims(model, isl_dim_out,
 300                                         0, isl_space_dim(model, isl_dim_out));
 301                 exp = isl_parameter_alignment_reordering(aff->ls->dim, model);
 302                 exp = isl_reordering_extend_space(exp,
 303                                         isl_aff_get_domain_space(aff));
 304                 aff = isl_aff_realign_domain(aff, exp);
 305         }
 306
 307         isl_space_free(model);
 308         return aff;
 309 error:
 310         isl_space_free(model);
 311         isl_aff_free(aff);
 312         return NULL;
 313 }
 314
 315 int isl_aff_plain_is_zero(__isl_keep isl_aff *aff)
 316 {
 317         if (!aff)
 318                 return -1;
 319
 320         return isl_seq_first_non_zero(aff->v->el + 1, aff->v->size - 1) < 0;
 321 }
 322
 323 int isl_aff_plain_is_equal(__isl_keep isl_aff *aff1, __isl_keep isl_aff *aff2)
 324 {
 325         int equal;
 326
 327         if (!aff1 || !aff2)
 328                 return -1;
 329
 330         equal = isl_local_space_is_equal(aff1->ls, aff2->ls);
 331         if (equal < 0 || !equal)
 332                 return equal;
 333
 334         return isl_vec_is_equal(aff1->v, aff2->v);
 335 }
 336
 337 int isl_aff_get_denominator(__isl_keep isl_aff *aff, isl_int *v)
 338 {
 339         if (!aff)
 340                 return -1;
 341         isl_int_set(*v, aff->v->el[0]);
 342         return 0;
 343 }
 344
 345 int isl_aff_get_constant(__isl_keep isl_aff *aff, isl_int *v)
 346 {
 347         if (!aff)
 348                 return -1;
 349         isl_int_set(*v, aff->v->el[1]);
 350         return 0;
 351 }
 352
 353 int isl_aff_get_coefficient(__isl_keep isl_aff *aff,
 354         enum isl_dim_type type, int pos, isl_int *v)
 355 {
 356         if (!aff)
 357                 return -1;
 358
 359         if (type == isl_dim_out)
 360                 isl_die(aff->v->ctx, isl_error_invalid,
 361                         "output/set dimension does not have a coefficient",
 362                         return -1);
 363         if (type == isl_dim_in)
 364                 type = isl_dim_set;
 365
 366         if (pos >= isl_local_space_dim(aff->ls, type))
 367                 isl_die(aff->v->ctx, isl_error_invalid,
 368                         "position out of bounds", return -1);
 369
 370         pos += isl_local_space_offset(aff->ls, type);
 371         isl_int_set(*v, aff->v->el[1 + pos]);
 372
 373         return 0;
 374 }
 375
 376 __isl_give isl_aff *isl_aff_set_denominator(__isl_take isl_aff *aff, isl_int v)
 377 {
 378         aff = isl_aff_cow(aff);
 379         if (!aff)
 380                 return NULL;
 381
 382         aff->v = isl_vec_cow(aff->v);
 383         if (!aff->v)
 384                 return isl_aff_free(aff);
 385
 386         isl_int_set(aff->v->el[0], v);
 387
 388         return aff;
 389 }
 390
 391 __isl_give isl_aff *isl_aff_set_constant(__isl_take isl_aff *aff, isl_int v)
 392 {
 393         aff = isl_aff_cow(aff);
 394         if (!aff)
 395                 return NULL;
 396
 397         aff->v = isl_vec_cow(aff->v);
 398         if (!aff->v)
 399                 return isl_aff_free(aff);
 400
 401         isl_int_set(aff->v->el[1], v);
 402
 403         return aff;
 404 }
 405
 406 __isl_give isl_aff *isl_aff_add_constant(__isl_take isl_aff *aff, isl_int v)
 407 {
 408         if (isl_int_is_zero(v))
 409                 return aff;
 410
 411         aff = isl_aff_cow(aff);
 412         if (!aff)
 413                 return NULL;
 414
 415         aff->v = isl_vec_cow(aff->v);
 416         if (!aff->v)
 417                 return isl_aff_free(aff);
 418
 419         isl_int_addmul(aff->v->el[1], aff->v->el[0], v);
 420
 421         return aff;
 422 }
 423
 424 __isl_give isl_aff *isl_aff_add_constant_si(__isl_take isl_aff *aff, int v)
 425 {
 426         isl_int t;
 427
 428         isl_int_init(t);
 429         isl_int_set_si(t, v);
 430         aff = isl_aff_add_constant(aff, t);
 431         isl_int_clear(t);
 432
 433         return aff;
 434 }
 435
 436 __isl_give isl_aff *isl_aff_set_constant_si(__isl_take isl_aff *aff, int v)
 437 {
 438         aff = isl_aff_cow(aff);
 439         if (!aff)
 440                 return NULL;
 441
 442         aff->v = isl_vec_cow(aff->v);
 443         if (!aff->v)
 444                 return isl_aff_free(aff);
 445
 446         isl_int_set_si(aff->v->el[1], v);
 447
 448         return aff;
 449 }
 450
 451 __isl_give isl_aff *isl_aff_set_coefficient(__isl_take isl_aff *aff,
 452         enum isl_dim_type type, int pos, isl_int v)
 453 {
 454         if (!aff)
 455                 return NULL;
 456
 457         if (type == isl_dim_out)
 458                 isl_die(aff->v->ctx, isl_error_invalid,
 459                         "output/set dimension does not have a coefficient",
 460                         return isl_aff_free(aff));
 461         if (type == isl_dim_in)
 462                 type = isl_dim_set;
 463
 464         if (pos >= isl_local_space_dim(aff->ls, type))
 465                 isl_die(aff->v->ctx, isl_error_invalid,
 466                         "position out of bounds", return isl_aff_free(aff));
 467
 468         aff = isl_aff_cow(aff);
 469         if (!aff)
 470                 return NULL;
 471
 472         aff->v = isl_vec_cow(aff->v);
 473         if (!aff->v)
 474                 return isl_aff_free(aff);
 475
 476         pos += isl_local_space_offset(aff->ls, type);
 477         isl_int_set(aff->v->el[1 + pos], v);
 478
 479         return aff;
 480 }
 481
 482 __isl_give isl_aff *isl_aff_set_coefficient_si(__isl_take isl_aff *aff,
 483         enum isl_dim_type type, int pos, int v)
 484 {
 485         if (!aff)
 486                 return NULL;
 487
 488         if (type == isl_dim_out)
 489                 isl_die(aff->v->ctx, isl_error_invalid,
 490                         "output/set dimension does not have a coefficient",
 491                         return isl_aff_free(aff));
 492         if (type == isl_dim_in)
 493                 type = isl_dim_set;
 494
 495         if (pos >= isl_local_space_dim(aff->ls, type))
 496                 isl_die(aff->v->ctx, isl_error_invalid,
 497                         "position out of bounds", return isl_aff_free(aff));
 498
 499         aff = isl_aff_cow(aff);
 500         if (!aff)
 501                 return NULL;
 502
 503         aff->v = isl_vec_cow(aff->v);
 504         if (!aff->v)
 505                 return isl_aff_free(aff);
 506
 507         pos += isl_local_space_offset(aff->ls, type);
 508         isl_int_set_si(aff->v->el[1 + pos], v);
 509
 510         return aff;
 511 }
 512
 513 __isl_give isl_aff *isl_aff_add_coefficient(__isl_take isl_aff *aff,
 514         enum isl_dim_type type, int pos, isl_int v)
 515 {
 516         if (!aff)
 517                 return NULL;
 518
 519         if (type == isl_dim_out)
 520                 isl_die(aff->v->ctx, isl_error_invalid,
 521                         "output/set dimension does not have a coefficient",
 522                         return isl_aff_free(aff));
 523         if (type == isl_dim_in)
 524                 type = isl_dim_set;
 525
 526         if (pos >= isl_local_space_dim(aff->ls, type))
 527                 isl_die(aff->v->ctx, isl_error_invalid,
 528                         "position out of bounds", return isl_aff_free(aff));
 529
 530         aff = isl_aff_cow(aff);
 531         if (!aff)
 532                 return NULL;
 533
 534         aff->v = isl_vec_cow(aff->v);
 535         if (!aff->v)
 536                 return isl_aff_free(aff);
 537
 538         pos += isl_local_space_offset(aff->ls, type);
 539         isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v);
 540
 541         return aff;
 542 }
 543
 544 __isl_give isl_aff *isl_aff_add_coefficient_si(__isl_take isl_aff *aff,
 545         enum isl_dim_type type, int pos, int v)
 546 {
 547         isl_int t;
 548
 549         isl_int_init(t);
 550         isl_int_set_si(t, v);
 551         aff = isl_aff_add_coefficient(aff, type, pos, t);
 552         isl_int_clear(t);
 553
 554         return aff;
 555 }
 556
 557 __isl_give isl_aff *isl_aff_get_div(__isl_keep isl_aff *aff, int pos)
 558 {
 559         if (!aff)
 560                 return NULL;
 561
 562         return isl_local_space_get_div(aff->ls, pos);
 563 }
 564
 565 __isl_give isl_aff *isl_aff_neg(__isl_take isl_aff *aff)
 566 {
 567         aff = isl_aff_cow(aff);
 568         if (!aff)
 569                 return NULL;
 570         aff->v = isl_vec_cow(aff->v);
 571         if (!aff->v)
 572                 return isl_aff_free(aff);
 573
 574         isl_seq_neg(aff->v->el + 1, aff->v->el + 1, aff->v->size - 1);
 575
 576         return aff;
 577 }
 578
 579 /* Remove divs from the local space that do not appear in the affine
 580  * expression.
 581  * We currently only remove divs at the end.
 582  * Some intermediate divs may also not appear directly in the affine
 583  * expression, but we would also need to check that no other divs are
 584  * defined in terms of them.
 585  */
 586 __isl_give isl_aff *isl_aff_remove_unused_divs( __isl_take isl_aff *aff)
 587 {
 588         int pos;
 589         int off;
 590         int n;
 591
 592         if (!aff)
 593                 return NULL;
 594
 595         n = isl_local_space_dim(aff->ls, isl_dim_div);
 596         off = isl_local_space_offset(aff->ls, isl_dim_div);
 597
 598         pos = isl_seq_last_non_zero(aff->v->el + 1 + off, n) + 1;
 599         if (pos == n)
 600                 return aff;
 601
 602         aff = isl_aff_cow(aff);
 603         if (!aff)
 604                 return NULL;
 605
 606         aff->ls = isl_local_space_drop_dims(aff->ls, isl_dim_div, pos, n - pos);
 607         aff->v = isl_vec_drop_els(aff->v, 1 + off + pos, n - pos);
 608         if (!aff->ls || !aff->v)
 609                 return isl_aff_free(aff);
 610
 611         return aff;
 612 }
 613
 614 __isl_give isl_aff *isl_aff_normalize(__isl_take isl_aff *aff)
 615 {
 616         if (!aff)
 617                 return NULL;
 618         aff->v = isl_vec_normalize(aff->v);
 619         if (!aff->v)
 620                 return isl_aff_free(aff);
 621         aff = isl_aff_remove_unused_divs(aff);
 622         return aff;
 623 }
 624
 625 /* Given f, return floor(f).
 626  * If f is an integer expression, then just return f.
 627  * If f is a constant, then return the constant floor(f).
 628  * Otherwise, if f = g/m, write g = q m + r,
 629  * create a new div d = [r/m] and return the expression q + d.
 630  * The coefficients in r are taken to lie between -m/2 and m/2.
 631  */
 632 __isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff)
 633 {
 634         int i;
 635         int size;
 636         isl_ctx *ctx;
 637         isl_vec *div;
 638
 639         if (!aff)
 640                 return NULL;
 641
 642         if (isl_int_is_one(aff->v->el[0]))
 643                 return aff;
 644
 645         aff = isl_aff_cow(aff);
 646         if (!aff)
 647                 return NULL;
 648
 649         aff->v = isl_vec_cow(aff->v);
 650         if (!aff->v)
 651                 return isl_aff_free(aff);
 652
 653         if (isl_aff_is_cst(aff)) {
 654                 isl_int_fdiv_q(aff->v->el[1], aff->v->el[1], aff->v->el[0]);
 655                 isl_int_set_si(aff->v->el[0], 1);
 656                 return aff;
 657         }
 658
 659         div = isl_vec_copy(aff->v);
 660         div = isl_vec_cow(div);
 661         if (!div)
 662                 return isl_aff_free(aff);
 663
 664         ctx = isl_aff_get_ctx(aff);
 665         isl_int_fdiv_q(aff->v->el[0], aff->v->el[0], ctx->two);
 666         for (i = 1; i < aff->v->size; ++i) {
 667                 isl_int_fdiv_r(div->el[i], div->el[i], div->el[0]);
 668                 isl_int_fdiv_q(aff->v->el[i], aff->v->el[i], div->el[0]);
 669                 if (isl_int_gt(div->el[i], aff->v->el[0])) {
 670                         isl_int_sub(div->el[i], div->el[i], div->el[0]);
 671                         isl_int_add_ui(aff->v->el[i], aff->v->el[i], 1);
 672                 }
 673         }
 674
 675         aff->ls = isl_local_space_add_div(aff->ls, div);
 676         if (!aff->ls)
 677                 return isl_aff_free(aff);
 678
 679         size = aff->v->size;
 680         aff->v = isl_vec_extend(aff->v, size + 1);
 681         if (!aff->v)
 682                 return isl_aff_free(aff);
 683         isl_int_set_si(aff->v->el[0], 1);
 684         isl_int_set_si(aff->v->el[size], 1);
 685
 686         return aff;
 687 }
 688
 689 /* Compute
 690  *
 691  *      aff mod m = aff - m * floor(aff/m)
 692  */
 693 __isl_give isl_aff *isl_aff_mod(__isl_take isl_aff *aff, isl_int m)
 694 {
 695         isl_aff *res;
 696
 697         res = isl_aff_copy(aff);
 698         aff = isl_aff_scale_down(aff, m);
 699         aff = isl_aff_floor(aff);
 700         aff = isl_aff_scale(aff, m);
 701         res = isl_aff_sub(res, aff);
 702
 703         return res;
 704 }
 705
 706 /* Compute
 707  *
 708  *      pwaff mod m = pwaff - m * floor(pwaff/m)
 709  */
 710 __isl_give isl_pw_aff *isl_pw_aff_mod(__isl_take isl_pw_aff *pwaff, isl_int m)
 711 {
 712         isl_pw_aff *res;
 713
 714         res = isl_pw_aff_copy(pwaff);
 715         pwaff = isl_pw_aff_scale_down(pwaff, m);
 716         pwaff = isl_pw_aff_floor(pwaff);
 717         pwaff = isl_pw_aff_scale(pwaff, m);
 718         res = isl_pw_aff_sub(res, pwaff);
 719
 720         return res;
 721 }
 722
 723 /* Given f, return ceil(f).
 724  * If f is an integer expression, then just return f.
 725  * Otherwise, create a new div d = [-f] and return the expression -d.
 726  */
 727 __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff)
 728 {
 729         if (!aff)
 730                 return NULL;
 731
 732         if (isl_int_is_one(aff->v->el[0]))
 733                 return aff;
 734
 735         aff = isl_aff_neg(aff);
 736         aff = isl_aff_floor(aff);
 737         aff = isl_aff_neg(aff);
 738
 739         return aff;
 740 }
 741
 742 /* Apply the expansion computed by isl_merge_divs.
 743  * The expansion itself is given by "exp" while the resulting
 744  * list of divs is given by "div".
 745  */
 746 __isl_give isl_aff *isl_aff_expand_divs( __isl_take isl_aff *aff,
 747         __isl_take isl_mat *div, int *exp)
 748 {
 749         int i, j;
 750         int old_n_div;
 751         int new_n_div;
 752         int offset;
 753
 754         aff = isl_aff_cow(aff);
 755         if (!aff || !div)
 756                 goto error;
 757
 758         old_n_div = isl_local_space_dim(aff->ls, isl_dim_div);
 759         new_n_div = isl_mat_rows(div);
 760         if (new_n_div < old_n_div)
 761                 isl_die(isl_mat_get_ctx(div), isl_error_invalid,
 762                         "not an expansion", goto error);
 763
 764         aff->v = isl_vec_extend(aff->v, aff->v->size + new_n_div - old_n_div);
 765         if (!aff->v)
 766                 goto error;
 767
 768         offset = 1 + isl_local_space_offset(aff->ls, isl_dim_div);
 769         j = old_n_div - 1;
 770         for (i = new_n_div - 1; i >= 0; --i) {
 771                 if (j >= 0 && exp[j] == i) {
 772                         if (i != j)
 773                                 isl_int_swap(aff->v->el[offset + i],
 774                                              aff->v->el[offset + j]);
 775                         j--;
 776                 } else
 777                         isl_int_set_si(aff->v->el[offset + i], 0);
 778         }
 779
 780         aff->ls = isl_local_space_replace_divs(aff->ls, isl_mat_copy(div));
 781         if (!aff->ls)
 782                 goto error;
 783         isl_mat_free(div);
 784         return aff;
 785 error:
 786         isl_aff_free(aff);
 787         isl_mat_free(div);
 788         return NULL;
 789 }
 790
 791 /* Add two affine expressions that live in the same local space.
 792  */
 793 static __isl_give isl_aff *add_expanded(__isl_take isl_aff *aff1,
 794         __isl_take isl_aff *aff2)
 795 {
 796         isl_int gcd, f;
 797
 798         aff1 = isl_aff_cow(aff1);
 799         if (!aff1 || !aff2)
 800                 goto error;
 801
 802         aff1->v = isl_vec_cow(aff1->v);
 803         if (!aff1->v)
 804                 goto error;
 805
 806         isl_int_init(gcd);
 807         isl_int_init(f);
 808         isl_int_gcd(gcd, aff1->v->el[0], aff2->v->el[0]);
 809         isl_int_divexact(f, aff2->v->el[0], gcd);
 810         isl_seq_scale(aff1->v->el + 1, aff1->v->el + 1, f, aff1->v->size - 1);
 811         isl_int_divexact(f, aff1->v->el[0], gcd);
 812         isl_seq_addmul(aff1->v->el + 1, f, aff2->v->el + 1, aff1->v->size - 1);
 813         isl_int_divexact(f, aff2->v->el[0], gcd);
 814         isl_int_mul(aff1->v->el[0], aff1->v->el[0], f);
 815         isl_int_clear(f);
 816         isl_int_clear(gcd);
 817
 818         isl_aff_free(aff2);
 819         return aff1;
 820 error:
 821         isl_aff_free(aff1);
 822         isl_aff_free(aff2);
 823         return NULL;
 824 }
 825
 826 __isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
 827         __isl_take isl_aff *aff2)
 828 {
 829         isl_ctx *ctx;
 830         int *exp1 = NULL;
 831         int *exp2 = NULL;
 832         isl_mat *div;
 833
 834         if (!aff1 || !aff2)
 835                 goto error;
 836
 837         ctx = isl_aff_get_ctx(aff1);
 838         if (!isl_space_is_equal(aff1->ls->dim, aff2->ls->dim))
 839                 isl_die(ctx, isl_error_invalid,
 840                         "spaces don't match", goto error);
 841
 842         if (aff1->ls->div->n_row == 0 && aff2->ls->div->n_row == 0)
 843                 return add_expanded(aff1, aff2);
 844
 845         exp1 = isl_alloc_array(ctx, int, aff1->ls->div->n_row);
 846         exp2 = isl_alloc_array(ctx, int, aff2->ls->div->n_row);
 847         if (!exp1 || !exp2)
 848                 goto error;
 849
 850         div = isl_merge_divs(aff1->ls->div, aff2->ls->div, exp1, exp2);
 851         aff1 = isl_aff_expand_divs(aff1, isl_mat_copy(div), exp1);
 852         aff2 = isl_aff_expand_divs(aff2, div, exp2);
 853         free(exp1);
 854         free(exp2);
 855
 856         return add_expanded(aff1, aff2);
 857 error:
 858         free(exp1);
 859         free(exp2);
 860         isl_aff_free(aff1);
 861         isl_aff_free(aff2);
 862         return NULL;
 863 }
 864
 865 __isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
 866         __isl_take isl_aff *aff2)
 867 {
 868         return isl_aff_add(aff1, isl_aff_neg(aff2));
 869 }
 870
 871 __isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f)
 872 {
 873         isl_int gcd;
 874
 875         if (isl_int_is_one(f))
 876                 return aff;
 877
 878         aff = isl_aff_cow(aff);
 879         if (!aff)
 880                 return NULL;
 881         aff->v = isl_vec_cow(aff->v);
 882         if (!aff->v)
 883                 return isl_aff_free(aff);
 884
 885         isl_int_init(gcd);
 886         isl_int_gcd(gcd, aff->v->el[0], f);
 887         isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd);
 888         isl_int_divexact(gcd, f, gcd);
 889         isl_seq_scale(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
 890         isl_int_clear(gcd);
 891
 892         return aff;
 893 }
 894
 895 __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f)
 896 {
 897         isl_int gcd;
 898
 899         if (isl_int_is_one(f))
 900                 return aff;
 901
 902         aff = isl_aff_cow(aff);
 903         if (!aff)
 904                 return NULL;
 905
 906         if (isl_int_is_zero(f))
 907                 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
 908                         "cannot scale down by zero", return isl_aff_free(aff));
 909
 910         aff->v = isl_vec_cow(aff->v);
 911         if (!aff->v)
 912                 return isl_aff_free(aff);
 913
 914         isl_int_init(gcd);
 915         isl_seq_gcd(aff->v->el + 1, aff->v->size - 1, &gcd);
 916         isl_int_gcd(gcd, gcd, f);
 917         isl_seq_scale_down(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
 918         isl_int_divexact(gcd, f, gcd);
 919         isl_int_mul(aff->v->el[0], aff->v->el[0], gcd);
 920         isl_int_clear(gcd);
 921
 922         return aff;
 923 }
 924
 925 __isl_give isl_aff *isl_aff_scale_down_ui(__isl_take isl_aff *aff, unsigned f)
 926 {
 927         isl_int v;
 928
 929         if (f == 1)
 930                 return aff;
 931
 932         isl_int_init(v);
 933         isl_int_set_ui(v, f);
 934         aff = isl_aff_scale_down(aff, v);
 935         isl_int_clear(v);
 936
 937         return aff;
 938 }
 939
 940 __isl_give isl_aff *isl_aff_set_dim_name(__isl_take isl_aff *aff,
 941         enum isl_dim_type type, unsigned pos, const char *s)
 942 {
 943         aff = isl_aff_cow(aff);
 944         if (!aff)
 945                 return NULL;
 946         if (type == isl_dim_out)
 947                 isl_die(aff->v->ctx, isl_error_invalid,
 948                         "cannot set name of output/set dimension",
 949                         return isl_aff_free(aff));
 950         if (type == isl_dim_in)
 951                 type = isl_dim_set;
 952         aff->ls = isl_local_space_set_dim_name(aff->ls, type, pos, s);
 953         if (!aff->ls)
 954                 return isl_aff_free(aff);
 955
 956         return aff;
 957 }
 958
 959 __isl_give isl_aff *isl_aff_set_dim_id(__isl_take isl_aff *aff,
 960         enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
 961 {
 962         aff = isl_aff_cow(aff);
 963         if (!aff)
 964                 return isl_id_free(id);
 965         if (type == isl_dim_out)
 966                 isl_die(aff->v->ctx, isl_error_invalid,
 967                         "cannot set name of output/set dimension",
 968                         goto error);
 969         if (type == isl_dim_in)
 970                 type = isl_dim_set;
 971         aff->ls = isl_local_space_set_dim_id(aff->ls, type, pos, id);
 972         if (!aff->ls)
 973                 return isl_aff_free(aff);
 974
 975         return aff;
 976 error:
 977         isl_id_free(id);
 978         isl_aff_free(aff);
 979         return NULL;
 980 }
 981
 982 /* Exploit the equalities in "eq" to simplify the affine expression
 983  * and the expressions of the integer divisions in the local space.
 984  * The integer divisions in this local space are assumed to appear
 985  * as regular dimensions in "eq".
 986  */
 987 static __isl_give isl_aff *isl_aff_substitute_equalities_lifted(
 988         __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
 989 {
 990         int i, j;
 991         unsigned total;
 992         unsigned n_div;
 993
 994         if (!eq)
 995                 goto error;
 996         if (eq->n_eq == 0) {
 997                 isl_basic_set_free(eq);
 998                 return aff;
 999         }
1000
1001         aff = isl_aff_cow(aff);
1002         if (!aff)
1003                 goto error;
1004
1005         aff->ls = isl_local_space_substitute_equalities(aff->ls,
1006                                                         isl_basic_set_copy(eq));
1007         if (!aff->ls)
1008                 goto error;
1009
1010         total = 1 + isl_space_dim(eq->dim, isl_dim_all);
1011         n_div = eq->n_div;
1012         for (i = 0; i < eq->n_eq; ++i) {
1013                 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
1014                 if (j < 0 || j == 0 || j >= total)
1015                         continue;
1016
1017                 isl_seq_elim(aff->v->el + 1, eq->eq[i], j, total,
1018                                 &aff->v->el[0]);
1019         }
1020
1021         isl_basic_set_free(eq);
1022         aff = isl_aff_normalize(aff);
1023         return aff;
1024 error:
1025         isl_basic_set_free(eq);
1026         isl_aff_free(aff);
1027         return NULL;
1028 }
1029
1030 /* Exploit the equalities in "eq" to simplify the affine expression
1031  * and the expressions of the integer divisions in the local space.
1032  */
1033 static __isl_give isl_aff *isl_aff_substitute_equalities(
1034         __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
1035 {
1036         int n_div;
1037
1038         if (!aff || !eq)
1039                 goto error;
1040         n_div = isl_local_space_dim(aff->ls, isl_dim_div);
1041         if (n_div > 0)
1042                 eq = isl_basic_set_add(eq, isl_dim_set, n_div);
1043         return isl_aff_substitute_equalities_lifted(aff, eq);
1044 error:
1045         isl_basic_set_free(eq);
1046         isl_aff_free(aff);
1047         return NULL;
1048 }
1049
1050 /* Look for equalities among the variables shared by context and aff
1051  * and the integer divisions of aff, if any.
1052  * The equalities are then used to eliminate coefficients and/or integer
1053  * divisions from aff.
1054  */
1055 __isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff,
1056         __isl_take isl_set *context)
1057 {
1058         isl_basic_set *hull;
1059         int n_div;
1060
1061         if (!aff)
1062                 goto error;
1063         n_div = isl_local_space_dim(aff->ls, isl_dim_div);
1064         if (n_div > 0) {
1065                 isl_basic_set *bset;
1066                 isl_local_space *ls;
1067                 context = isl_set_add_dims(context, isl_dim_set, n_div);
1068                 ls = isl_aff_get_domain_local_space(aff);
1069                 bset = isl_basic_set_from_local_space(ls);
1070                 bset = isl_basic_set_lift(bset);
1071                 bset = isl_basic_set_flatten(bset);
1072                 context = isl_set_intersect(context,
1073                                             isl_set_from_basic_set(bset));
1074         }
1075
1076         hull = isl_set_affine_hull(context);
1077         return isl_aff_substitute_equalities_lifted(aff, hull);
1078 error:
1079         isl_aff_free(aff);
1080         isl_set_free(context);
1081         return NULL;
1082 }
1083
1084 __isl_give isl_aff *isl_aff_gist_params(__isl_take isl_aff *aff,
1085         __isl_take isl_set *context)
1086 {
1087         isl_set *dom_context = isl_set_universe(isl_aff_get_domain_space(aff));
1088         dom_context = isl_set_intersect_params(dom_context, context);
1089         return isl_aff_gist(aff, dom_context);
1090 }
1091
1092 /* Return a basic set containing those elements in the space
1093  * of aff where it is non-negative.
1094  */
1095 __isl_give isl_basic_set *isl_aff_nonneg_basic_set(__isl_take isl_aff *aff)
1096 {
1097         isl_constraint *ineq;
1098         isl_basic_set *bset;
1099
1100         ineq = isl_inequality_from_aff(aff);
1101
1102         bset = isl_basic_set_from_constraint(ineq);
1103         bset = isl_basic_set_simplify(bset);
1104         return bset;
1105 }
1106
1107 /* Return a basic set containing those elements in the space
1108  * of aff where it is zero.
1109  */
1110 __isl_give isl_basic_set *isl_aff_zero_basic_set(__isl_take isl_aff *aff)
1111 {
1112         isl_constraint *ineq;
1113         isl_basic_set *bset;
1114
1115         ineq = isl_equality_from_aff(aff);
1116
1117         bset = isl_basic_set_from_constraint(ineq);
1118         bset = isl_basic_set_simplify(bset);
1119         return bset;
1120 }
1121
1122 /* Return a basic set containing those elements in the shared space
1123  * of aff1 and aff2 where aff1 is greater than or equal to aff2.
1124  */
1125 __isl_give isl_basic_set *isl_aff_ge_basic_set(__isl_take isl_aff *aff1,
1126         __isl_take isl_aff *aff2)
1127 {
1128         aff1 = isl_aff_sub(aff1, aff2);
1129
1130         return isl_aff_nonneg_basic_set(aff1);
1131 }
1132
1133 /* Return a basic set containing those elements in the shared space
1134  * of aff1 and aff2 where aff1 is smaller than or equal to aff2.
1135  */
1136 __isl_give isl_basic_set *isl_aff_le_basic_set(__isl_take isl_aff *aff1,
1137         __isl_take isl_aff *aff2)
1138 {
1139         return isl_aff_ge_basic_set(aff2, aff1);
1140 }
1141
1142 __isl_give isl_aff *isl_aff_add_on_domain(__isl_keep isl_set *dom,
1143         __isl_take isl_aff *aff1, __isl_take isl_aff *aff2)
1144 {
1145         aff1 = isl_aff_add(aff1, aff2);
1146         aff1 = isl_aff_gist(aff1, isl_set_copy(dom));
1147         return aff1;
1148 }
1149
1150 int isl_aff_is_empty(__isl_keep isl_aff *aff)
1151 {
1152         if (!aff)
1153                 return -1;
1154
1155         return 0;
1156 }
1157
1158 /* Check whether the given affine expression has non-zero coefficient
1159  * for any dimension in the given range or if any of these dimensions
1160  * appear with non-zero coefficients in any of the integer divisions
1161  * involved in the affine expression.
1162  */
1163 int isl_aff_involves_dims(__isl_keep isl_aff *aff,
1164         enum isl_dim_type type, unsigned first, unsigned n)
1165 {
1166         int i;
1167         isl_ctx *ctx;
1168         int *active = NULL;
1169         int involves = 0;
1170
1171         if (!aff)
1172                 return -1;
1173         if (n == 0)
1174                 return 0;
1175
1176         ctx = isl_aff_get_ctx(aff);
1177         if (first + n > isl_aff_dim(aff, type))
1178                 isl_die(ctx, isl_error_invalid,
1179                         "range out of bounds", return -1);
1180
1181         active = isl_local_space_get_active(aff->ls, aff->v->el + 2);
1182         if (!active)
1183                 goto error;
1184
1185         first += isl_local_space_offset(aff->ls, type) - 1;
1186         for (i = 0; i < n; ++i)
1187                 if (active[first + i]) {
1188                         involves = 1;
1189                         break;
1190                 }
1191
1192         free(active);
1193
1194         return involves;
1195 error:
1196         free(active);
1197         return -1;
1198 }
1199
1200 __isl_give isl_aff *isl_aff_drop_dims(__isl_take isl_aff *aff,
1201         enum isl_dim_type type, unsigned first, unsigned n)
1202 {
1203         isl_ctx *ctx;
1204
1205         if (!aff)
1206                 return NULL;
1207         if (type == isl_dim_out)
1208                 isl_die(aff->v->ctx, isl_error_invalid,
1209                         "cannot drop output/set dimension",
1210                         return isl_aff_free(aff));
1211         if (type == isl_dim_in)
1212                 type = isl_dim_set;
1213         if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
1214                 return aff;
1215
1216         ctx = isl_aff_get_ctx(aff);
1217         if (first + n > isl_local_space_dim(aff->ls, type))
1218                 isl_die(ctx, isl_error_invalid, "range out of bounds",
1219                         return isl_aff_free(aff));
1220
1221         aff = isl_aff_cow(aff);
1222         if (!aff)
1223                 return NULL;
1224
1225         aff->ls = isl_local_space_drop_dims(aff->ls, type, first, n);
1226         if (!aff->ls)
1227                 return isl_aff_free(aff);
1228
1229         first += 1 + isl_local_space_offset(aff->ls, type);
1230         aff->v = isl_vec_drop_els(aff->v, first, n);
1231         if (!aff->v)
1232                 return isl_aff_free(aff);
1233
1234         return aff;
1235 }
1236
1237 /* Project the domain of the affine expression onto its parameter space.
1238  * The affine expression may not involve any of the domain dimensions.
1239  */
1240 __isl_give isl_aff *isl_aff_project_domain_on_params(__isl_take isl_aff *aff)
1241 {
1242         isl_space *space;
1243         unsigned n;
1244         int involves;
1245
1246         n = isl_aff_dim(aff, isl_dim_in);
1247         involves = isl_aff_involves_dims(aff, isl_dim_in, 0, n);
1248         if (involves < 0)
1249                 return isl_aff_free(aff);
1250         if (involves)
1251                 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
1252                     "affine expression involves some of the domain dimensions",
1253                     return isl_aff_free(aff));
1254         aff = isl_aff_drop_dims(aff, isl_dim_in, 0, n);
1255         space = isl_aff_get_domain_space(aff);
1256         space = isl_space_params(space);
1257         aff = isl_aff_reset_domain_space(aff, space);
1258         return aff;
1259 }
1260
1261 __isl_give isl_aff *isl_aff_insert_dims(__isl_take isl_aff *aff,
1262         enum isl_dim_type type, unsigned first, unsigned n)
1263 {
1264         isl_ctx *ctx;
1265
1266         if (!aff)
1267                 return NULL;
1268         if (type == isl_dim_out)
1269                 isl_die(aff->v->ctx, isl_error_invalid,
1270                         "cannot insert output/set dimensions",
1271                         return isl_aff_free(aff));
1272         if (type == isl_dim_in)
1273                 type = isl_dim_set;
1274         if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
1275                 return aff;
1276
1277         ctx = isl_aff_get_ctx(aff);
1278         if (first > isl_local_space_dim(aff->ls, type))
1279                 isl_die(ctx, isl_error_invalid, "position out of bounds",
1280                         return isl_aff_free(aff));
1281
1282         aff = isl_aff_cow(aff);
1283         if (!aff)
1284                 return NULL;
1285
1286         aff->ls = isl_local_space_insert_dims(aff->ls, type, first, n);
1287         if (!aff->ls)
1288                 return isl_aff_free(aff);
1289
1290         first += 1 + isl_local_space_offset(aff->ls, type);
1291         aff->v = isl_vec_insert_zero_els(aff->v, first, n);
1292         if (!aff->v)
1293                 return isl_aff_free(aff);
1294
1295         return aff;
1296 }
1297
1298 __isl_give isl_aff *isl_aff_add_dims(__isl_take isl_aff *aff,
1299         enum isl_dim_type type, unsigned n)
1300 {
1301         unsigned pos;
1302
1303         pos = isl_aff_dim(aff, type);
1304
1305         return isl_aff_insert_dims(aff, type, pos, n);
1306 }
1307
1308 __isl_give isl_pw_aff *isl_pw_aff_add_dims(__isl_take isl_pw_aff *pwaff,
1309         enum isl_dim_type type, unsigned n)
1310 {
1311         unsigned pos;
1312
1313         pos = isl_pw_aff_dim(pwaff, type);
1314
1315         return isl_pw_aff_insert_dims(pwaff, type, pos, n);
1316 }
1317
1318 __isl_give isl_pw_aff *isl_pw_aff_from_aff(__isl_take isl_aff *aff)
1319 {
1320         isl_set *dom = isl_set_universe(isl_aff_get_domain_space(aff));
1321         return isl_pw_aff_alloc(dom, aff);
1322 }
1323
1324 #undef PW
1325 #define PW isl_pw_aff
1326 #undef EL
1327 #define EL isl_aff
1328 #undef EL_IS_ZERO
1329 #define EL_IS_ZERO is_empty
1330 #undef ZERO
1331 #define ZERO empty
1332 #undef IS_ZERO
1333 #define IS_ZERO is_empty
1334 #undef FIELD
1335 #define FIELD aff
1336 #undef DEFAULT_IS_ZERO
1337 #define DEFAULT_IS_ZERO 0
1338
1339 #define NO_EVAL
1340 #define NO_OPT
1341 #define NO_MOVE_DIMS
1342 #define NO_LIFT
1343 #define NO_MORPH
1344
1345 #include <isl_pw_templ.c>
1346
1347 static __isl_give isl_set *align_params_pw_pw_set_and(
1348         __isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2,
1349         __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1350                                     __isl_take isl_pw_aff *pwaff2))
1351 {
1352         if (!pwaff1 || !pwaff2)
1353                 goto error;
1354         if (isl_space_match(pwaff1->dim, isl_dim_param,
1355                           pwaff2->dim, isl_dim_param))
1356                 return fn(pwaff1, pwaff2);
1357         if (!isl_space_has_named_params(pwaff1->dim) ||
1358             !isl_space_has_named_params(pwaff2->dim))
1359                 isl_die(isl_pw_aff_get_ctx(pwaff1), isl_error_invalid,
1360                         "unaligned unnamed parameters", goto error);
1361         pwaff1 = isl_pw_aff_align_params(pwaff1, isl_pw_aff_get_space(pwaff2));
1362         pwaff2 = isl_pw_aff_align_params(pwaff2, isl_pw_aff_get_space(pwaff1));
1363         return fn(pwaff1, pwaff2);
1364 error:
1365         isl_pw_aff_free(pwaff1);
1366         isl_pw_aff_free(pwaff2);
1367         return NULL;
1368 }
1369
1370 /* Compute a piecewise quasi-affine expression with a domain that
1371  * is the union of those of pwaff1 and pwaff2 and such that on each
1372  * cell, the quasi-affine expression is the better (according to cmp)
1373  * of those of pwaff1 and pwaff2.  If only one of pwaff1 or pwaff2
1374  * is defined on a given cell, then the associated expression
1375  * is the defined one.
1376  */
1377 static __isl_give isl_pw_aff *pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1378         __isl_take isl_pw_aff *pwaff2,
1379         __isl_give isl_basic_set *(*cmp)(__isl_take isl_aff *aff1,
1380                                         __isl_take isl_aff *aff2))
1381 {
1382         int i, j, n;
1383         isl_pw_aff *res;
1384         isl_ctx *ctx;
1385         isl_set *set;
1386
1387         if (!pwaff1 || !pwaff2)
1388                 goto error;
1389
1390         ctx = isl_space_get_ctx(pwaff1->dim);
1391         if (!isl_space_is_equal(pwaff1->dim, pwaff2->dim))
1392                 isl_die(ctx, isl_error_invalid,
1393                         "arguments should live in same space", goto error);
1394
1395         if (isl_pw_aff_is_empty(pwaff1)) {
1396                 isl_pw_aff_free(pwaff1);
1397                 return pwaff2;
1398         }
1399
1400         if (isl_pw_aff_is_empty(pwaff2)) {
1401                 isl_pw_aff_free(pwaff2);
1402                 return pwaff1;
1403         }
1404
1405         n = 2 * (pwaff1->n + 1) * (pwaff2->n + 1);
1406         res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n);
1407
1408         for (i = 0; i < pwaff1->n; ++i) {
1409                 set = isl_set_copy(pwaff1->p[i].set);
1410                 for (j = 0; j < pwaff2->n; ++j) {
1411                         struct isl_set *common;
1412                         isl_set *better;
1413
1414                         common = isl_set_intersect(
1415                                         isl_set_copy(pwaff1->p[i].set),
1416                                         isl_set_copy(pwaff2->p[j].set));
1417                         better = isl_set_from_basic_set(cmp(
1418                                         isl_aff_copy(pwaff2->p[j].aff),
1419                                         isl_aff_copy(pwaff1->p[i].aff)));
1420                         better = isl_set_intersect(common, better);
1421                         if (isl_set_plain_is_empty(better)) {
1422                                 isl_set_free(better);
1423                                 continue;
1424                         }
1425                         set = isl_set_subtract(set, isl_set_copy(better));
1426
1427                         res = isl_pw_aff_add_piece(res, better,
1428                                                 isl_aff_copy(pwaff2->p[j].aff));
1429                 }
1430                 res = isl_pw_aff_add_piece(res, set,
1431                                                 isl_aff_copy(pwaff1->p[i].aff));
1432         }
1433
1434         for (j = 0; j < pwaff2->n; ++j) {
1435                 set = isl_set_copy(pwaff2->p[j].set);
1436                 for (i = 0; i < pwaff1->n; ++i)
1437                         set = isl_set_subtract(set,
1438                                         isl_set_copy(pwaff1->p[i].set));
1439                 res = isl_pw_aff_add_piece(res, set,
1440                                                 isl_aff_copy(pwaff2->p[j].aff));
1441         }
1442
1443         isl_pw_aff_free(pwaff1);
1444         isl_pw_aff_free(pwaff2);
1445
1446         return res;
1447 error:
1448         isl_pw_aff_free(pwaff1);
1449         isl_pw_aff_free(pwaff2);
1450         return NULL;
1451 }
1452
1453 /* Compute a piecewise quasi-affine expression with a domain that
1454  * is the union of those of pwaff1 and pwaff2 and such that on each
1455  * cell, the quasi-affine expression is the maximum of those of pwaff1
1456  * and pwaff2.  If only one of pwaff1 or pwaff2 is defined on a given
1457  * cell, then the associated expression is the defined one.
1458  */
1459 static __isl_give isl_pw_aff *pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1460         __isl_take isl_pw_aff *pwaff2)
1461 {
1462         return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_ge_basic_set);
1463 }
1464
1465 __isl_give isl_pw_aff *isl_pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1466         __isl_take isl_pw_aff *pwaff2)
1467 {
1468         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2,
1469                                                         &pw_aff_union_max);
1470 }
1471
1472 /* Compute a piecewise quasi-affine expression with a domain that
1473  * is the union of those of pwaff1 and pwaff2 and such that on each
1474  * cell, the quasi-affine expression is the minimum of those of pwaff1
1475  * and pwaff2.  If only one of pwaff1 or pwaff2 is defined on a given
1476  * cell, then the associated expression is the defined one.
1477  */
1478 static __isl_give isl_pw_aff *pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1479         __isl_take isl_pw_aff *pwaff2)
1480 {
1481         return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_le_basic_set);
1482 }
1483
1484 __isl_give isl_pw_aff *isl_pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1485         __isl_take isl_pw_aff *pwaff2)
1486 {
1487         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2,
1488                                                         &pw_aff_union_min);
1489 }
1490
1491 __isl_give isl_pw_aff *isl_pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1492         __isl_take isl_pw_aff *pwaff2, int max)
1493 {
1494         if (max)
1495                 return isl_pw_aff_union_max(pwaff1, pwaff2);
1496         else
1497                 return isl_pw_aff_union_min(pwaff1, pwaff2);
1498 }
1499
1500 /* Construct a map with as domain the domain of pwaff and
1501  * one-dimensional range corresponding to the affine expressions.
1502  */
1503 static __isl_give isl_map *map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1504 {
1505         int i;
1506         isl_space *dim;
1507         isl_map *map;
1508
1509         if (!pwaff)
1510                 return NULL;
1511
1512         dim = isl_pw_aff_get_space(pwaff);
1513         map = isl_map_empty(dim);
1514
1515         for (i = 0; i < pwaff->n; ++i) {
1516                 isl_basic_map *bmap;
1517                 isl_map *map_i;
1518
1519                 bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
1520                 map_i = isl_map_from_basic_map(bmap);
1521                 map_i = isl_map_intersect_domain(map_i,
1522                                                 isl_set_copy(pwaff->p[i].set));
1523                 map = isl_map_union_disjoint(map, map_i);
1524         }
1525
1526         isl_pw_aff_free(pwaff);
1527
1528         return map;
1529 }
1530
1531 /* Construct a map with as domain the domain of pwaff and
1532  * one-dimensional range corresponding to the affine expressions.
1533  */
1534 __isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1535 {
1536         if (!pwaff)
1537                 return NULL;
1538         if (isl_space_is_set(pwaff->dim))
1539                 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1540                         "space of input is not a map",
1541                         return isl_pw_aff_free(pwaff));
1542         return map_from_pw_aff(pwaff);
1543 }
1544
1545 /* Construct a one-dimensional set with as parameter domain
1546  * the domain of pwaff and the single set dimension
1547  * corresponding to the affine expressions.
1548  */
1549 __isl_give isl_set *isl_set_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1550 {
1551         if (!pwaff)
1552                 return NULL;
1553         if (!isl_space_is_set(pwaff->dim))
1554                 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1555                         "space of input is not a set",
1556                         return isl_pw_aff_free(pwaff));
1557         return map_from_pw_aff(pwaff);
1558 }
1559
1560 /* Return a set containing those elements in the domain
1561  * of pwaff where it is non-negative.
1562  */
1563 __isl_give isl_set *isl_pw_aff_nonneg_set(__isl_take isl_pw_aff *pwaff)
1564 {
1565         int i;
1566         isl_set *set;
1567
1568         if (!pwaff)
1569                 return NULL;
1570
1571         set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1572
1573         for (i = 0; i < pwaff->n; ++i) {
1574                 isl_basic_set *bset;
1575                 isl_set *set_i;
1576
1577                 bset = isl_aff_nonneg_basic_set(isl_aff_copy(pwaff->p[i].aff));
1578                 set_i = isl_set_from_basic_set(bset);
1579                 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1580                 set = isl_set_union_disjoint(set, set_i);
1581         }
1582
1583         isl_pw_aff_free(pwaff);
1584
1585         return set;
1586 }
1587
1588 /* Return a set containing those elements in the domain
1589  * of pwaff where it is zero (if complement is 0) or not zero
1590  * (if complement is 1).
1591  */
1592 static __isl_give isl_set *pw_aff_zero_set(__isl_take isl_pw_aff *pwaff,
1593         int complement)
1594 {
1595         int i;
1596         isl_set *set;
1597
1598         if (!pwaff)
1599                 return NULL;
1600
1601         set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1602
1603         for (i = 0; i < pwaff->n; ++i) {
1604                 isl_basic_set *bset;
1605                 isl_set *set_i, *zero;
1606
1607                 bset = isl_aff_zero_basic_set(isl_aff_copy(pwaff->p[i].aff));
1608                 zero = isl_set_from_basic_set(bset);
1609                 set_i = isl_set_copy(pwaff->p[i].set);
1610                 if (complement)
1611                         set_i = isl_set_subtract(set_i, zero);
1612                 else
1613                         set_i = isl_set_intersect(set_i, zero);
1614                 set = isl_set_union_disjoint(set, set_i);
1615         }
1616
1617         isl_pw_aff_free(pwaff);
1618
1619         return set;
1620 }
1621
1622 /* Return a set containing those elements in the domain
1623  * of pwaff where it is zero.
1624  */
1625 __isl_give isl_set *isl_pw_aff_zero_set(__isl_take isl_pw_aff *pwaff)
1626 {
1627         return pw_aff_zero_set(pwaff, 0);
1628 }
1629
1630 /* Return a set containing those elements in the domain
1631  * of pwaff where it is not zero.
1632  */
1633 __isl_give isl_set *isl_pw_aff_non_zero_set(__isl_take isl_pw_aff *pwaff)
1634 {
1635         return pw_aff_zero_set(pwaff, 1);
1636 }
1637
1638 /* Return a set containing those elements in the shared domain
1639  * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
1640  *
1641  * We compute the difference on the shared domain and then construct
1642  * the set of values where this difference is non-negative.
1643  * If strict is set, we first subtract 1 from the difference.
1644  * If equal is set, we only return the elements where pwaff1 and pwaff2
1645  * are equal.
1646  */
1647 static __isl_give isl_set *pw_aff_gte_set(__isl_take isl_pw_aff *pwaff1,
1648         __isl_take isl_pw_aff *pwaff2, int strict, int equal)
1649 {
1650         isl_set *set1, *set2;
1651
1652         set1 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff1));
1653         set2 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff2));
1654         set1 = isl_set_intersect(set1, set2);
1655         pwaff1 = isl_pw_aff_intersect_domain(pwaff1, isl_set_copy(set1));
1656         pwaff2 = isl_pw_aff_intersect_domain(pwaff2, isl_set_copy(set1));
1657         pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_neg(pwaff2));
1658
1659         if (strict) {
1660                 isl_space *dim = isl_set_get_space(set1);
1661                 isl_aff *aff;
1662                 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
1663                 aff = isl_aff_add_constant_si(aff, -1);
1664                 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_alloc(set1, aff));
1665         } else
1666                 isl_set_free(set1);
1667
1668         if (equal)
1669                 return isl_pw_aff_zero_set(pwaff1);
1670         return isl_pw_aff_nonneg_set(pwaff1);
1671 }
1672
1673 /* Return a set containing those elements in the shared domain
1674  * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
1675  */
1676 static __isl_give isl_set *pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1677         __isl_take isl_pw_aff *pwaff2)
1678 {
1679         return pw_aff_gte_set(pwaff1, pwaff2, 0, 1);
1680 }
1681
1682 __isl_give isl_set *isl_pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1683         __isl_take isl_pw_aff *pwaff2)
1684 {
1685         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_eq_set);
1686 }
1687
1688 /* Return a set containing those elements in the shared domain
1689  * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
1690  */
1691 static __isl_give isl_set *pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1692         __isl_take isl_pw_aff *pwaff2)
1693 {
1694         return pw_aff_gte_set(pwaff1, pwaff2, 0, 0);
1695 }
1696
1697 __isl_give isl_set *isl_pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1698         __isl_take isl_pw_aff *pwaff2)
1699 {
1700         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ge_set);
1701 }
1702
1703 /* Return a set containing those elements in the shared domain
1704  * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
1705  */
1706 static __isl_give isl_set *pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1707         __isl_take isl_pw_aff *pwaff2)
1708 {
1709         return pw_aff_gte_set(pwaff1, pwaff2, 1, 0);
1710 }
1711
1712 __isl_give isl_set *isl_pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1713         __isl_take isl_pw_aff *pwaff2)
1714 {
1715         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_gt_set);
1716 }
1717
1718 __isl_give isl_set *isl_pw_aff_le_set(__isl_take isl_pw_aff *pwaff1,
1719         __isl_take isl_pw_aff *pwaff2)
1720 {
1721         return isl_pw_aff_ge_set(pwaff2, pwaff1);
1722 }
1723
1724 __isl_give isl_set *isl_pw_aff_lt_set(__isl_take isl_pw_aff *pwaff1,
1725         __isl_take isl_pw_aff *pwaff2)
1726 {
1727         return isl_pw_aff_gt_set(pwaff2, pwaff1);
1728 }
1729
1730 /* Return a set containing those elements in the shared domain
1731  * of the elements of list1 and list2 where each element in list1
1732  * has the relation specified by "fn" with each element in list2.
1733  */
1734 static __isl_give isl_set *pw_aff_list_set(__isl_take isl_pw_aff_list *list1,
1735         __isl_take isl_pw_aff_list *list2,
1736         __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1737                                     __isl_take isl_pw_aff *pwaff2))
1738 {
1739         int i, j;
1740         isl_ctx *ctx;
1741         isl_set *set;
1742
1743         if (!list1 || !list2)
1744                 goto error;
1745
1746         ctx = isl_pw_aff_list_get_ctx(list1);
1747         if (list1->n < 1 || list2->n < 1)
1748                 isl_die(ctx, isl_error_invalid,
1749                         "list should contain at least one element", goto error);
1750
1751         set = isl_set_universe(isl_pw_aff_get_domain_space(list1->p[0]));
1752         for (i = 0; i < list1->n; ++i)
1753                 for (j = 0; j < list2->n; ++j) {
1754                         isl_set *set_ij;
1755
1756                         set_ij = fn(isl_pw_aff_copy(list1->p[i]),
1757                                     isl_pw_aff_copy(list2->p[j]));
1758                         set = isl_set_intersect(set, set_ij);
1759                 }
1760
1761         isl_pw_aff_list_free(list1);
1762         isl_pw_aff_list_free(list2);
1763         return set;
1764 error:
1765         isl_pw_aff_list_free(list1);
1766         isl_pw_aff_list_free(list2);
1767         return NULL;
1768 }
1769
1770 /* Return a set containing those elements in the shared domain
1771  * of the elements of list1 and list2 where each element in list1
1772  * is equal to each element in list2.
1773  */
1774 __isl_give isl_set *isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list *list1,
1775         __isl_take isl_pw_aff_list *list2)
1776 {
1777         return pw_aff_list_set(list1, list2, &isl_pw_aff_eq_set);
1778 }
1779
1780 __isl_give isl_set *isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list *list1,
1781         __isl_take isl_pw_aff_list *list2)
1782 {
1783         return pw_aff_list_set(list1, list2, &isl_pw_aff_ne_set);
1784 }
1785
1786 /* Return a set containing those elements in the shared domain
1787  * of the elements of list1 and list2 where each element in list1
1788  * is less than or equal to each element in list2.
1789  */
1790 __isl_give isl_set *isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list *list1,
1791         __isl_take isl_pw_aff_list *list2)
1792 {
1793         return pw_aff_list_set(list1, list2, &isl_pw_aff_le_set);
1794 }
1795
1796 __isl_give isl_set *isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list *list1,
1797         __isl_take isl_pw_aff_list *list2)
1798 {
1799         return pw_aff_list_set(list1, list2, &isl_pw_aff_lt_set);
1800 }
1801
1802 __isl_give isl_set *isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list *list1,
1803         __isl_take isl_pw_aff_list *list2)
1804 {
1805         return pw_aff_list_set(list1, list2, &isl_pw_aff_ge_set);
1806 }
1807
1808 __isl_give isl_set *isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list *list1,
1809         __isl_take isl_pw_aff_list *list2)
1810 {
1811         return pw_aff_list_set(list1, list2, &isl_pw_aff_gt_set);
1812 }
1813
1814
1815 /* Return a set containing those elements in the shared domain
1816  * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
1817  */
1818 static __isl_give isl_set *pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1819         __isl_take isl_pw_aff *pwaff2)
1820 {
1821         isl_set *set_lt, *set_gt;
1822
1823         set_lt = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1),
1824                                    isl_pw_aff_copy(pwaff2));
1825         set_gt = isl_pw_aff_gt_set(pwaff1, pwaff2);
1826         return isl_set_union_disjoint(set_lt, set_gt);
1827 }
1828
1829 __isl_give isl_set *isl_pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1830         __isl_take isl_pw_aff *pwaff2)
1831 {
1832         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ne_set);
1833 }
1834
1835 __isl_give isl_pw_aff *isl_pw_aff_scale_down(__isl_take isl_pw_aff *pwaff,
1836         isl_int v)
1837 {
1838         int i;
1839
1840         if (isl_int_is_one(v))
1841                 return pwaff;
1842         if (!isl_int_is_pos(v))
1843                 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1844                         "factor needs to be positive",
1845                         return isl_pw_aff_free(pwaff));
1846         pwaff = isl_pw_aff_cow(pwaff);
1847         if (!pwaff)
1848                 return NULL;
1849         if (pwaff->n == 0)
1850                 return pwaff;
1851
1852         for (i = 0; i < pwaff->n; ++i) {
1853                 pwaff->p[i].aff = isl_aff_scale_down(pwaff->p[i].aff, v);
1854                 if (!pwaff->p[i].aff)
1855                         return isl_pw_aff_free(pwaff);
1856         }
1857
1858         return pwaff;
1859 }
1860
1861 __isl_give isl_pw_aff *isl_pw_aff_floor(__isl_take isl_pw_aff *pwaff)
1862 {
1863         int i;
1864
1865         pwaff = isl_pw_aff_cow(pwaff);
1866         if (!pwaff)
1867                 return NULL;
1868         if (pwaff->n == 0)
1869                 return pwaff;
1870
1871         for (i = 0; i < pwaff->n; ++i) {
1872                 pwaff->p[i].aff = isl_aff_floor(pwaff->p[i].aff);
1873                 if (!pwaff->p[i].aff)
1874                         return isl_pw_aff_free(pwaff);
1875         }
1876
1877         return pwaff;
1878 }
1879
1880 __isl_give isl_pw_aff *isl_pw_aff_ceil(__isl_take isl_pw_aff *pwaff)
1881 {
1882         int i;
1883
1884         pwaff = isl_pw_aff_cow(pwaff);
1885         if (!pwaff)
1886                 return NULL;
1887         if (pwaff->n == 0)
1888                 return pwaff;
1889
1890         for (i = 0; i < pwaff->n; ++i) {
1891                 pwaff->p[i].aff = isl_aff_ceil(pwaff->p[i].aff);
1892                 if (!pwaff->p[i].aff)
1893                         return isl_pw_aff_free(pwaff);
1894         }
1895
1896         return pwaff;
1897 }
1898
1899 /* Assuming that "cond1" and "cond2" are disjoint,
1900  * return an affine expression that is equal to pwaff1 on cond1
1901  * and to pwaff2 on cond2.
1902  */
1903 static __isl_give isl_pw_aff *isl_pw_aff_select(
1904         __isl_take isl_set *cond1, __isl_take isl_pw_aff *pwaff1,
1905         __isl_take isl_set *cond2, __isl_take isl_pw_aff *pwaff2)
1906 {
1907         pwaff1 = isl_pw_aff_intersect_domain(pwaff1, cond1);
1908         pwaff2 = isl_pw_aff_intersect_domain(pwaff2, cond2);
1909
1910         return isl_pw_aff_add_disjoint(pwaff1, pwaff2);
1911 }
1912
1913 /* Return an affine expression that is equal to pwaff_true for elements
1914  * where "cond" is non-zero and to pwaff_false for elements where "cond"
1915  * is zero.
1916  * That is, return cond ? pwaff_true : pwaff_false;
1917  */
1918 __isl_give isl_pw_aff *isl_pw_aff_cond(__isl_take isl_pw_aff *cond,
1919         __isl_take isl_pw_aff *pwaff_true, __isl_take isl_pw_aff *pwaff_false)
1920 {
1921         isl_set *cond_true, *cond_false;
1922
1923         cond_true = isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond));
1924         cond_false = isl_pw_aff_zero_set(cond);
1925         return isl_pw_aff_select(cond_true, pwaff_true,
1926                                  cond_false, pwaff_false);
1927 }
1928
1929 int isl_aff_is_cst(__isl_keep isl_aff *aff)
1930 {
1931         if (!aff)
1932                 return -1;
1933
1934         return isl_seq_first_non_zero(aff->v->el + 2, aff->v->size - 2) == -1;
1935 }
1936
1937 /* Check whether pwaff is a piecewise constant.
1938  */
1939 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff)
1940 {
1941         int i;
1942
1943         if (!pwaff)
1944                 return -1;
1945
1946         for (i = 0; i < pwaff->n; ++i) {
1947                 int is_cst = isl_aff_is_cst(pwaff->p[i].aff);
1948                 if (is_cst < 0 || !is_cst)
1949                         return is_cst;
1950         }
1951
1952         return 1;
1953 }
1954
1955 __isl_give isl_aff *isl_aff_mul(__isl_take isl_aff *aff1,
1956         __isl_take isl_aff *aff2)
1957 {
1958         if (!isl_aff_is_cst(aff2) && isl_aff_is_cst(aff1))
1959                 return isl_aff_mul(aff2, aff1);
1960
1961         if (!isl_aff_is_cst(aff2))
1962                 isl_die(isl_aff_get_ctx(aff1), isl_error_invalid,
1963                         "at least one affine expression should be constant",
1964                         goto error);
1965
1966         aff1 = isl_aff_cow(aff1);
1967         if (!aff1 || !aff2)
1968                 goto error;
1969
1970         aff1 = isl_aff_scale(aff1, aff2->v->el[1]);
1971         aff1 = isl_aff_scale_down(aff1, aff2->v->el[0]);
1972
1973         isl_aff_free(aff2);
1974         return aff1;
1975 error:
1976         isl_aff_free(aff1);
1977         isl_aff_free(aff2);
1978         return NULL;
1979 }
1980
1981 static __isl_give isl_pw_aff *pw_aff_add(__isl_take isl_pw_aff *pwaff1,
1982         __isl_take isl_pw_aff *pwaff2)
1983 {
1984         return isl_pw_aff_on_shared_domain(pwaff1, pwaff2, &isl_aff_add);
1985 }
1986
1987 __isl_give isl_pw_aff *isl_pw_aff_add(__isl_take isl_pw_aff *pwaff1,
1988         __isl_take isl_pw_aff *pwaff2)
1989 {
1990         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_add);
1991 }
1992
1993 __isl_give isl_pw_aff *isl_pw_aff_union_add(__isl_take isl_pw_aff *pwaff1,
1994         __isl_take isl_pw_aff *pwaff2)
1995 {
1996         return isl_pw_aff_union_add_(pwaff1, pwaff2);
1997 }
1998
1999 static __isl_give isl_pw_aff *pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
2000         __isl_take isl_pw_aff *pwaff2)
2001 {
2002         return isl_pw_aff_on_shared_domain(pwaff1, pwaff2, &isl_aff_mul);
2003 }
2004
2005 __isl_give isl_pw_aff *isl_pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
2006         __isl_take isl_pw_aff *pwaff2)
2007 {
2008         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_mul);
2009 }
2010
2011 static __isl_give isl_pw_aff *pw_aff_min(__isl_take isl_pw_aff *pwaff1,
2012         __isl_take isl_pw_aff *pwaff2)
2013 {
2014         isl_set *le;
2015         isl_set *dom;
2016
2017         dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1)),
2018                                 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2)));
2019         le = isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1),
2020                                 isl_pw_aff_copy(pwaff2));
2021         dom = isl_set_subtract(dom, isl_set_copy(le));
2022         return isl_pw_aff_select(le, pwaff1, dom, pwaff2);
2023 }
2024
2025 __isl_give isl_pw_aff *isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1,
2026         __isl_take isl_pw_aff *pwaff2)
2027 {
2028         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_min);
2029 }
2030
2031 static __isl_give isl_pw_aff *pw_aff_max(__isl_take isl_pw_aff *pwaff1,
2032         __isl_take isl_pw_aff *pwaff2)
2033 {
2034         isl_set *ge;
2035         isl_set *dom;
2036
2037         dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1)),
2038                                 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2)));
2039         ge = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1),
2040                                 isl_pw_aff_copy(pwaff2));
2041         dom = isl_set_subtract(dom, isl_set_copy(ge));
2042         return isl_pw_aff_select(ge, pwaff1, dom, pwaff2);
2043 }
2044
2045 __isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1,
2046         __isl_take isl_pw_aff *pwaff2)
2047 {
2048         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_max);
2049 }
2050
2051 static __isl_give isl_pw_aff *pw_aff_list_reduce(
2052         __isl_take isl_pw_aff_list *list,
2053         __isl_give isl_pw_aff *(*fn)(__isl_take isl_pw_aff *pwaff1,
2054                                         __isl_take isl_pw_aff *pwaff2))
2055 {
2056         int i;
2057         isl_ctx *ctx;
2058         isl_pw_aff *res;
2059
2060         if (!list)
2061                 return NULL;
2062
2063         ctx = isl_pw_aff_list_get_ctx(list);
2064         if (list->n < 1)
2065                 isl_die(ctx, isl_error_invalid,
2066                         "list should contain at least one element",
2067                         return isl_pw_aff_list_free(list));
2068
2069         res = isl_pw_aff_copy(list->p[0]);
2070         for (i = 1; i < list->n; ++i)
2071                 res = fn(res, isl_pw_aff_copy(list->p[i]));
2072
2073         isl_pw_aff_list_free(list);
2074         return res;
2075 }
2076
2077 /* Return an isl_pw_aff that maps each element in the intersection of the
2078  * domains of the elements of list to the minimal corresponding affine
2079  * expression.
2080  */
2081 __isl_give isl_pw_aff *isl_pw_aff_list_min(__isl_take isl_pw_aff_list *list)
2082 {
2083         return pw_aff_list_reduce(list, &isl_pw_aff_min);
2084 }
2085
2086 /* Return an isl_pw_aff that maps each element in the intersection of the
2087  * domains of the elements of list to the maximal corresponding affine
2088  * expression.
2089  */
2090 __isl_give isl_pw_aff *isl_pw_aff_list_max(__isl_take isl_pw_aff_list *list)
2091 {
2092         return pw_aff_list_reduce(list, &isl_pw_aff_max);
2093 }
2094
2095 #undef BASE
2096 #define BASE aff
2097
2098 #include <isl_multi_templ.c>
2099
2100 /* Construct an isl_multi_aff in the given space with value zero in
2101  * each of the output dimensions.
2102  */
2103 __isl_give isl_multi_aff *isl_multi_aff_zero(__isl_take isl_space *space)
2104 {
2105         int n;
2106         isl_multi_aff *ma;
2107
2108         if (!space)
2109                 return NULL;
2110
2111         n = isl_space_dim(space , isl_dim_out);
2112         ma = isl_multi_aff_alloc(isl_space_copy(space));
2113
2114         if (!n)
2115                 isl_space_free(space);
2116         else {
2117                 int i;
2118                 isl_local_space *ls;
2119                 isl_aff *aff;
2120
2121                 space = isl_space_domain(space);
2122                 ls = isl_local_space_from_space(space);
2123                 aff = isl_aff_zero_on_domain(ls);
2124
2125                 for (i = 0; i < n; ++i)
2126                         ma = isl_multi_aff_set_aff(ma, i, isl_aff_copy(aff));
2127
2128                 isl_aff_free(aff);
2129         }
2130
2131         return ma;
2132 }
2133
2134 /* Create an isl_pw_multi_aff with the given isl_multi_aff on a universe
2135  * domain.
2136  */
2137 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_multi_aff(
2138         __isl_take isl_multi_aff *ma)
2139 {
2140         isl_set *dom = isl_set_universe(isl_multi_aff_get_domain_space(ma));
2141         return isl_pw_multi_aff_alloc(dom, ma);
2142 }
2143
2144 __isl_give isl_multi_aff *isl_multi_aff_add(__isl_take isl_multi_aff *maff1,
2145         __isl_take isl_multi_aff *maff2)
2146 {
2147         int i;
2148         isl_ctx *ctx;
2149
2150         maff1 = isl_multi_aff_cow(maff1);
2151         if (!maff1 || !maff2)
2152                 goto error;
2153
2154         ctx = isl_multi_aff_get_ctx(maff1);
2155         if (!isl_space_is_equal(maff1->space, maff2->space))
2156                 isl_die(ctx, isl_error_invalid,
2157                         "spaces don't match", goto error);
2158
2159         for (i = 0; i < maff1->n; ++i) {
2160                 maff1->p[i] = isl_aff_add(maff1->p[i],
2161                                             isl_aff_copy(maff2->p[i]));
2162                 if (!maff1->p[i])
2163                         goto error;
2164         }
2165
2166         isl_multi_aff_free(maff2);
2167         return maff1;
2168 error:
2169         isl_multi_aff_free(maff1);
2170         isl_multi_aff_free(maff2);
2171         return NULL;
2172 }
2173
2174 /* Exploit the equalities in "eq" to simplify the affine expressions.
2175  */
2176 static __isl_give isl_multi_aff *isl_multi_aff_substitute_equalities(
2177         __isl_take isl_multi_aff *maff, __isl_take isl_basic_set *eq)
2178 {
2179         int i;
2180
2181         maff = isl_multi_aff_cow(maff);
2182         if (!maff || !eq)
2183                 goto error;
2184
2185         for (i = 0; i < maff->n; ++i) {
2186                 maff->p[i] = isl_aff_substitute_equalities(maff->p[i],
2187                                                     isl_basic_set_copy(eq));
2188                 if (!maff->p[i])
2189                         goto error;
2190         }
2191
2192         isl_basic_set_free(eq);
2193         return maff;
2194 error:
2195         isl_basic_set_free(eq);
2196         isl_multi_aff_free(maff);
2197         return NULL;
2198 }
2199
2200 __isl_give isl_multi_aff *isl_multi_aff_scale(__isl_take isl_multi_aff *maff,
2201         isl_int f)
2202 {
2203         int i;
2204
2205         maff = isl_multi_aff_cow(maff);
2206         if (!maff)
2207                 return NULL;
2208
2209         for (i = 0; i < maff->n; ++i) {
2210                 maff->p[i] = isl_aff_scale(maff->p[i], f);
2211                 if (!maff->p[i])
2212                         return isl_multi_aff_free(maff);
2213         }
2214
2215         return maff;
2216 }
2217
2218 __isl_give isl_multi_aff *isl_multi_aff_add_on_domain(__isl_keep isl_set *dom,
2219         __isl_take isl_multi_aff *maff1, __isl_take isl_multi_aff *maff2)
2220 {
2221         maff1 = isl_multi_aff_add(maff1, maff2);
2222         maff1 = isl_multi_aff_gist(maff1, isl_set_copy(dom));
2223         return maff1;
2224 }
2225
2226 int isl_multi_aff_is_empty(__isl_keep isl_multi_aff *maff)
2227 {
2228         if (!maff)
2229                 return -1;
2230
2231         return 0;
2232 }
2233
2234 int isl_multi_aff_plain_is_equal(__isl_keep isl_multi_aff *maff1,
2235         __isl_keep isl_multi_aff *maff2)
2236 {
2237         int i;
2238         int equal;
2239
2240         if (!maff1 || !maff2)
2241                 return -1;
2242         if (maff1->n != maff2->n)
2243                 return 0;
2244         equal = isl_space_is_equal(maff1->space, maff2->space);
2245         if (equal < 0 || !equal)
2246                 return equal;
2247
2248         for (i = 0; i < maff1->n; ++i) {
2249                 equal = isl_aff_plain_is_equal(maff1->p[i], maff2->p[i]);
2250                 if (equal < 0 || !equal)
2251                         return equal;
2252         }
2253
2254         return 1;
2255 }
2256
2257 __isl_give isl_multi_aff *isl_multi_aff_set_dim_name(
2258         __isl_take isl_multi_aff *maff,
2259         enum isl_dim_type type, unsigned pos, const char *s)
2260 {
2261         int i;
2262
2263         maff = isl_multi_aff_cow(maff);
2264         if (!maff)
2265                 return NULL;
2266
2267         maff->space = isl_space_set_dim_name(maff->space, type, pos, s);
2268         if (!maff->space)
2269                 return isl_multi_aff_free(maff);
2270
2271         if (type == isl_dim_out)
2272                 return maff;
2273         for (i = 0; i < maff->n; ++i) {
2274                 maff->p[i] = isl_aff_set_dim_name(maff->p[i], type, pos, s);
2275                 if (!maff->p[i])
2276                         return isl_multi_aff_free(maff);
2277         }
2278
2279         return maff;
2280 }
2281
2282 __isl_give isl_multi_aff *isl_multi_aff_drop_dims(__isl_take isl_multi_aff *maff,
2283         enum isl_dim_type type, unsigned first, unsigned n)
2284 {
2285         int i;
2286
2287         maff = isl_multi_aff_cow(maff);
2288         if (!maff)
2289                 return NULL;
2290
2291         maff->space = isl_space_drop_dims(maff->space, type, first, n);
2292         if (!maff->space)
2293                 return isl_multi_aff_free(maff);
2294
2295         if (type == isl_dim_out) {
2296                 for (i = 0; i < n; ++i)
2297                         isl_aff_free(maff->p[first + i]);
2298                 for (i = first; i + n < maff->n; ++i)
2299                         maff->p[i] = maff->p[i + n];
2300                 maff->n -= n;
2301                 return maff;
2302         }
2303
2304         for (i = 0; i < maff->n; ++i) {
2305                 maff->p[i] = isl_aff_drop_dims(maff->p[i], type, first, n);
2306                 if (!maff->p[i])
2307                         return isl_multi_aff_free(maff);
2308         }
2309
2310         return maff;
2311 }
2312
2313 #undef PW
2314 #define PW isl_pw_multi_aff
2315 #undef EL
2316 #define EL isl_multi_aff
2317 #undef EL_IS_ZERO
2318 #define EL_IS_ZERO is_empty
2319 #undef ZERO
2320 #define ZERO empty
2321 #undef IS_ZERO
2322 #define IS_ZERO is_empty
2323 #undef FIELD
2324 #define FIELD maff
2325 #undef DEFAULT_IS_ZERO
2326 #define DEFAULT_IS_ZERO 0
2327
2328 #define NO_NEG
2329 #define NO_EVAL
2330 #define NO_OPT
2331 #define NO_INVOLVES_DIMS
2332 #define NO_MOVE_DIMS
2333 #define NO_INSERT_DIMS
2334 #define NO_LIFT
2335 #define NO_MORPH
2336
2337 #include <isl_pw_templ.c>
2338
2339 #undef UNION
2340 #define UNION isl_union_pw_multi_aff
2341 #undef PART
2342 #define PART isl_pw_multi_aff
2343 #undef PARTS
2344 #define PARTS pw_multi_aff
2345 #define ALIGN_DOMAIN
2346
2347 #define NO_EVAL
2348
2349 #include <isl_union_templ.c>
2350
2351 static __isl_give isl_pw_multi_aff *pw_multi_aff_add(
2352         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
2353 {
2354         return isl_pw_multi_aff_on_shared_domain(pma1, pma2,
2355                                                 &isl_multi_aff_add);
2356 }
2357
2358 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_add(
2359         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
2360 {
2361         return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
2362                                                 &pw_multi_aff_add);
2363 }
2364
2365 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_add(
2366         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
2367 {
2368         return isl_pw_multi_aff_union_add_(pma1, pma2);
2369 }
2370
2371 /* Construct a map mapping the domain of the piecewise multi-affine expression
2372  * to its range, with each dimension in the range equated to the
2373  * corresponding affine expression on its cell.
2374  */
2375 __isl_give isl_map *isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
2376 {
2377         int i;
2378         isl_map *map;
2379
2380         if (!pma)
2381                 return NULL;
2382
2383         map = isl_map_empty(isl_pw_multi_aff_get_space(pma));
2384
2385         for (i = 0; i < pma->n; ++i) {
2386                 isl_multi_aff *maff;
2387                 isl_basic_map *bmap;
2388                 isl_map *map_i;
2389
2390                 maff = isl_multi_aff_copy(pma->p[i].maff);
2391                 bmap = isl_basic_map_from_multi_aff(maff);
2392                 map_i = isl_map_from_basic_map(bmap);
2393                 map_i = isl_map_intersect_domain(map_i,
2394                                                 isl_set_copy(pma->p[i].set));
2395                 map = isl_map_union_disjoint(map, map_i);
2396         }
2397
2398         isl_pw_multi_aff_free(pma);
2399         return map;
2400 }
2401
2402 __isl_give isl_set *isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
2403 {
2404         if (!isl_space_is_set(pma->dim))
2405                 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
2406                         "isl_pw_multi_aff cannot be converted into an isl_set",
2407                         return isl_pw_multi_aff_free(pma));
2408
2409         return isl_map_from_pw_multi_aff(pma);
2410 }
2411
2412 /* Given a basic map with a single output dimension that is defined
2413  * in terms of the parameters and input dimensions using an equality,
2414  * extract an isl_aff that expresses the output dimension in terms
2415  * of the parameters and input dimensions.
2416  *
2417  * Since some applications expect the result of isl_pw_multi_aff_from_map
2418  * to only contain integer affine expressions, we compute the floor
2419  * of the expression before returning.
2420  *
2421  * This function shares some similarities with
2422  * isl_basic_map_has_defining_equality and isl_constraint_get_bound.
2423  */
2424 static __isl_give isl_aff *extract_isl_aff_from_basic_map(
2425         __isl_take isl_basic_map *bmap)
2426 {
2427         int i;
2428         unsigned offset;
2429         unsigned total;
2430         isl_local_space *ls;
2431         isl_aff *aff;
2432
2433         if (!bmap)
2434                 return NULL;
2435         if (isl_basic_map_dim(bmap, isl_dim_out) != 1)
2436                 isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
2437                         "basic map should have a single output dimension",
2438                         goto error);
2439         offset = isl_basic_map_offset(bmap, isl_dim_out);
2440         total = isl_basic_map_total_dim(bmap);
2441         for (i = 0; i < bmap->n_eq; ++i) {
2442                 if (isl_int_is_zero(bmap->eq[i][offset]))
2443                         continue;
2444                 if (isl_seq_first_non_zero(bmap->eq[i] + offset + 1,
2445                                            1 + total - (offset + 1)) != -1)
2446                         continue;
2447                 break;
2448         }
2449         if (i >= bmap->n_eq)
2450                 isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
2451                         "unable to find suitable equality", goto error);
2452         ls = isl_basic_map_get_local_space(bmap);
2453         aff = isl_aff_alloc(isl_local_space_domain(ls));
2454         if (!aff)
2455                 goto error;
2456         if (isl_int_is_neg(bmap->eq[i][offset]))
2457                 isl_seq_cpy(aff->v->el + 1, bmap->eq[i], offset);
2458         else
2459                 isl_seq_neg(aff->v->el + 1, bmap->eq[i], offset);
2460         isl_seq_clr(aff->v->el + 1 + offset, aff->v->size - (1 + offset));
2461         isl_int_abs(aff->v->el[0], bmap->eq[i][offset]);
2462         isl_basic_map_free(bmap);
2463
2464         aff = isl_aff_remove_unused_divs(aff);
2465         aff = isl_aff_floor(aff);
2466         return aff;
2467 error:
2468         isl_basic_map_free(bmap);
2469         return NULL;
2470 }
2471
2472 /* Given a basic map where each output dimension is defined
2473  * in terms of the parameters and input dimensions using an equality,
2474  * extract an isl_multi_aff that expresses the output dimensions in terms
2475  * of the parameters and input dimensions.
2476  */
2477 static __isl_give isl_multi_aff *extract_isl_multi_aff_from_basic_map(
2478         __isl_take isl_basic_map *bmap)
2479 {
2480         int i;
2481         unsigned n_out;
2482         isl_multi_aff *ma;
2483
2484         if (!bmap)
2485                 return NULL;
2486
2487         ma = isl_multi_aff_alloc(isl_basic_map_get_space(bmap));
2488         n_out = isl_basic_map_dim(bmap, isl_dim_out);
2489
2490         for (i = 0; i < n_out; ++i) {
2491                 isl_basic_map *bmap_i;
2492                 isl_aff *aff;
2493
2494                 bmap_i = isl_basic_map_copy(bmap);
2495                 bmap_i = isl_basic_map_project_out(bmap_i, isl_dim_out,
2496                                                         i + 1, n_out - (1 + i));
2497                 bmap_i = isl_basic_map_project_out(bmap_i, isl_dim_out, 0, i);
2498                 aff = extract_isl_aff_from_basic_map(bmap_i);
2499                 ma = isl_multi_aff_set_aff(ma, i, aff);
2500         }
2501
2502         isl_basic_map_free(bmap);
2503
2504         return ma;
2505 }
2506
2507 /* Create an isl_pw_multi_aff that is equivalent to
2508  * isl_map_intersect_domain(isl_map_from_basic_map(bmap), domain).
2509  * The given basic map is such that each output dimension is defined
2510  * in terms of the parameters and input dimensions using an equality.
2511  */
2512 static __isl_give isl_pw_multi_aff *plain_pw_multi_aff_from_map(
2513         __isl_take isl_set *domain, __isl_take isl_basic_map *bmap)
2514 {
2515         isl_multi_aff *ma;
2516
2517         ma = extract_isl_multi_aff_from_basic_map(bmap);
2518         return isl_pw_multi_aff_alloc(domain, ma);
2519 }
2520
2521 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
2522  * This obivously only works if the input "map" is single-valued.
2523  * If so, we compute the lexicographic minimum of the image in the form
2524  * of an isl_pw_multi_aff.  Since the image is unique, it is equal
2525  * to its lexicographic minimum.
2526  * If the input is not single-valued, we produce an error.
2527  *
2528  * As a special case, we first check if all output dimensions are uniquely
2529  * defined in terms of the parameters and input dimensions over the entire
2530  * domain.  If so, we extract the desired isl_pw_multi_aff directly
2531  * from the affine hull of "map" and its domain.
2532  */
2533 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_map(__isl_take isl_map *map)
2534 {
2535         int i;
2536         int sv;
2537         isl_pw_multi_aff *pma;
2538         isl_basic_map *hull;
2539
2540         if (!map)
2541                 return NULL;
2542
2543         hull = isl_map_affine_hull(isl_map_copy(map));
2544         sv = isl_basic_map_plain_is_single_valued(hull);
2545         if (sv >= 0 && sv)
2546                 return plain_pw_multi_aff_from_map(isl_map_domain(map), hull);
2547         isl_basic_map_free(hull);
2548         if (sv < 0)
2549                 goto error;
2550
2551         sv = isl_map_is_single_valued(map);
2552         if (sv < 0)
2553                 goto error;
2554         if (!sv)
2555                 isl_die(isl_map_get_ctx(map), isl_error_invalid,
2556                         "map is not single-valued", goto error);
2557         map = isl_map_make_disjoint(map);
2558         if (!map)
2559                 return NULL;
2560
2561         pma = isl_pw_multi_aff_empty(isl_map_get_space(map));
2562
2563         for (i = 0; i < map->n; ++i) {
2564                 isl_pw_multi_aff *pma_i;
2565                 isl_basic_map *bmap;
2566                 bmap = isl_basic_map_copy(map->p[i]);
2567                 pma_i = isl_basic_map_lexmin_pw_multi_aff(bmap);
2568                 pma = isl_pw_multi_aff_add_disjoint(pma, pma_i);
2569         }
2570
2571         isl_map_free(map);
2572         return pma;
2573 error:
2574         isl_map_free(map);
2575         return NULL;
2576 }
2577
2578 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_set(__isl_take isl_set *set)
2579 {
2580         return isl_pw_multi_aff_from_map(set);
2581 }
2582
2583 /* Return the piecewise affine expression "set ? 1 : 0".
2584  */
2585 __isl_give isl_pw_aff *isl_set_indicator_function(__isl_take isl_set *set)
2586 {
2587         isl_pw_aff *pa;
2588         isl_space *space = isl_set_get_space(set);
2589         isl_local_space *ls = isl_local_space_from_space(space);
2590         isl_aff *zero = isl_aff_zero_on_domain(isl_local_space_copy(ls));
2591         isl_aff *one = isl_aff_zero_on_domain(ls);
2592
2593         one = isl_aff_add_constant_si(one, 1);
2594         pa = isl_pw_aff_alloc(isl_set_copy(set), one);
2595         set = isl_set_complement(set);
2596         pa = isl_pw_aff_add_disjoint(pa, isl_pw_aff_alloc(set, zero));
2597
2598         return pa;
2599 }
2600
2601 /* Plug in "subs" for dimension "type", "pos" of "aff".
2602  *
2603  * Let i be the dimension to replace and let "subs" be of the form
2604  *
2605  *      f/d
2606  *
2607  * and "aff" of the form
2608  *
2609  *      (a i + g)/m
2610  *
2611  * The result is
2612  *
2613  *      floor((a f + d g')/(m d))
2614  *
2615  * where g' is the result of plugging in "subs" in each of the integer
2616  * divisions in g.
2617  */
2618 __isl_give isl_aff *isl_aff_substitute(__isl_take isl_aff *aff,
2619         enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs)
2620 {
2621         isl_ctx *ctx;
2622         isl_int v;
2623
2624         aff = isl_aff_cow(aff);
2625         if (!aff || !subs)
2626                 return isl_aff_free(aff);
2627
2628         ctx = isl_aff_get_ctx(aff);
2629         if (!isl_space_is_equal(aff->ls->dim, subs->ls->dim))
2630                 isl_die(ctx, isl_error_invalid,
2631                         "spaces don't match", return isl_aff_free(aff));
2632         if (isl_local_space_dim(subs->ls, isl_dim_div) != 0)
2633                 isl_die(ctx, isl_error_unsupported,
2634                         "cannot handle divs yet", return isl_aff_free(aff));
2635
2636         aff->ls = isl_local_space_substitute(aff->ls, type, pos, subs);
2637         if (!aff->ls)
2638                 return isl_aff_free(aff);
2639
2640         aff->v = isl_vec_cow(aff->v);
2641         if (!aff->v)
2642                 return isl_aff_free(aff);
2643
2644         pos += isl_local_space_offset(aff->ls, type);
2645
2646         isl_int_init(v);
2647         isl_int_set(v, aff->v->el[1 + pos]);
2648         isl_int_set_si(aff->v->el[1 + pos], 0);
2649         isl_seq_combine(aff->v->el + 1, subs->v->el[0], aff->v->el + 1,
2650                         v, subs->v->el + 1, subs->v->size - 1);
2651         isl_int_mul(aff->v->el[0], aff->v->el[0], subs->v->el[0]);
2652         isl_int_clear(v);
2653
2654         return aff;
2655 }
2656
2657 /* Plug in "subs" for dimension "type", "pos" in each of the affine
2658  * expressions in "maff".
2659  */
2660 __isl_give isl_multi_aff *isl_multi_aff_substitute(
2661         __isl_take isl_multi_aff *maff, enum isl_dim_type type, unsigned pos,
2662         __isl_keep isl_aff *subs)
2663 {
2664         int i;
2665
2666         maff = isl_multi_aff_cow(maff);
2667         if (!maff || !subs)
2668                 return isl_multi_aff_free(maff);
2669
2670         if (type == isl_dim_in)
2671                 type = isl_dim_set;
2672
2673         for (i = 0; i < maff->n; ++i) {
2674                 maff->p[i] = isl_aff_substitute(maff->p[i], type, pos, subs);
2675                 if (!maff->p[i])
2676                         return isl_multi_aff_free(maff);
2677         }
2678
2679         return maff;
2680 }
2681
2682 /* Plug in "subs" for dimension "type", "pos" of "pma".
2683  *
2684  * pma is of the form
2685  *
2686  *      A_i(v) -> M_i(v)
2687  *
2688  * while subs is of the form
2689  *
2690  *      v' = B_j(v) -> S_j
2691  *
2692  * Each pair i,j such that C_ij = A_i \cap B_i is non-empty
2693  * has a contribution in the result, in particular
2694  *
2695  *      C_ij(S_j) -> M_i(S_j)
2696  *
2697  * Note that plugging in S_j in C_ij may also result in an empty set
2698  * and this contribution should simply be discarded.
2699  */
2700 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_substitute(
2701         __isl_take isl_pw_multi_aff *pma, enum isl_dim_type type, unsigned pos,
2702         __isl_keep isl_pw_aff *subs)
2703 {
2704         int i, j, n;
2705         isl_pw_multi_aff *res;
2706
2707         if (!pma || !subs)
2708                 return isl_pw_multi_aff_free(pma);
2709
2710         n = pma->n * subs->n;
2711         res = isl_pw_multi_aff_alloc_size(isl_space_copy(pma->dim), n);
2712
2713         for (i = 0; i < pma->n; ++i) {
2714                 for (j = 0; j < subs->n; ++j) {
2715                         isl_set *common;
2716                         isl_multi_aff *res_ij;
2717                         common = isl_set_intersect(
2718                                         isl_set_copy(pma->p[i].set),
2719                                         isl_set_copy(subs->p[j].set));
2720                         common = isl_set_substitute(common,
2721                                         type, pos, subs->p[j].aff);
2722                         if (isl_set_plain_is_empty(common)) {
2723                                 isl_set_free(common);
2724                                 continue;
2725                         }
2726
2727                         res_ij = isl_multi_aff_substitute(
2728                                         isl_multi_aff_copy(pma->p[i].maff),
2729                                         type, pos, subs->p[j].aff);
2730
2731                         res = isl_pw_multi_aff_add_piece(res, common, res_ij);
2732                 }
2733         }
2734
2735         isl_pw_multi_aff_free(pma);
2736         return res;
2737 }
2738
2739 /* Extend the local space of "dst" to include the divs
2740  * in the local space of "src".
2741  */
2742 __isl_give isl_aff *isl_aff_align_divs(__isl_take isl_aff *dst,
2743         __isl_keep isl_aff *src)
2744 {
2745         isl_ctx *ctx;
2746         int *exp1 = NULL;
2747         int *exp2 = NULL;
2748         isl_mat *div;
2749
2750         if (!src || !dst)
2751                 return isl_aff_free(dst);
2752
2753         ctx = isl_aff_get_ctx(src);
2754         if (!isl_space_is_equal(src->ls->dim, dst->ls->dim))
2755                 isl_die(ctx, isl_error_invalid,
2756                         "spaces don't match", goto error);
2757
2758         if (src->ls->div->n_row == 0)
2759                 return dst;
2760
2761         exp1 = isl_alloc_array(ctx, int, src->ls->div->n_row);
2762         exp2 = isl_alloc_array(ctx, int, dst->ls->div->n_row);
2763         if (!exp1 || !exp2)
2764                 goto error;
2765
2766         div = isl_merge_divs(src->ls->div, dst->ls->div, exp1, exp2);
2767         dst = isl_aff_expand_divs(dst, div, exp2);
2768         free(exp1);
2769         free(exp2);
2770
2771         return dst;
2772 error:
2773         free(exp1);
2774         free(exp2);
2775         return isl_aff_free(dst);
2776 }
2777
2778 /* Adjust the local spaces of the affine expressions in "maff"
2779  * such that they all have the save divs.
2780  */
2781 __isl_give isl_multi_aff *isl_multi_aff_align_divs(
2782         __isl_take isl_multi_aff *maff)
2783 {
2784         int i;
2785
2786         if (!maff)
2787                 return NULL;
2788         if (maff->n == 0)
2789                 return maff;
2790         maff = isl_multi_aff_cow(maff);
2791         if (!maff)
2792                 return NULL;
2793
2794         for (i = 1; i < maff->n; ++i)
2795                 maff->p[0] = isl_aff_align_divs(maff->p[0], maff->p[i]);
2796         for (i = 1; i < maff->n; ++i) {
2797                 maff->p[i] = isl_aff_align_divs(maff->p[i], maff->p[0]);
2798                 if (!maff->p[i])
2799                         return isl_multi_aff_free(maff);
2800         }
2801
2802         return maff;
2803 }
2804
2805 __isl_give isl_aff *isl_aff_lift(__isl_take isl_aff *aff)
2806 {
2807         aff = isl_aff_cow(aff);
2808         if (!aff)
2809                 return NULL;
2810
2811         aff->ls = isl_local_space_lift(aff->ls);
2812         if (!aff->ls)
2813                 return isl_aff_free(aff);
2814
2815         return aff;
2816 }
2817
2818 /* Lift "maff" to a space with extra dimensions such that the result
2819  * has no more existentially quantified variables.
2820  * If "ls" is not NULL, then *ls is assigned the local space that lies
2821  * at the basis of the lifting applied to "maff".
2822  */
2823 __isl_give isl_multi_aff *isl_multi_aff_lift(__isl_take isl_multi_aff *maff,
2824         __isl_give isl_local_space **ls)
2825 {
2826         int i;
2827         isl_space *space;
2828         unsigned n_div;
2829
2830         if (ls)
2831                 *ls = NULL;
2832
2833         if (!maff)
2834                 return NULL;
2835
2836         if (maff->n == 0) {
2837                 if (ls) {
2838                         isl_space *space = isl_multi_aff_get_domain_space(maff);
2839                         *ls = isl_local_space_from_space(space);
2840                         if (!*ls)
2841                                 return isl_multi_aff_free(maff);
2842                 }
2843                 return maff;
2844         }
2845
2846         maff = isl_multi_aff_cow(maff);
2847         maff = isl_multi_aff_align_divs(maff);
2848         if (!maff)
2849                 return NULL;
2850
2851         n_div = isl_aff_dim(maff->p[0], isl_dim_div);
2852         space = isl_multi_aff_get_space(maff);
2853         space = isl_space_lift(isl_space_domain(space), n_div);
2854         space = isl_space_extend_domain_with_range(space,
2855                                                 isl_multi_aff_get_space(maff));
2856         if (!space)
2857                 return isl_multi_aff_free(maff);
2858         isl_space_free(maff->space);
2859         maff->space = space;
2860
2861         if (ls) {
2862                 *ls = isl_aff_get_domain_local_space(maff->p[0]);
2863                 if (!*ls)
2864                         return isl_multi_aff_free(maff);
2865         }
2866
2867         for (i = 0; i < maff->n; ++i) {
2868                 maff->p[i] = isl_aff_lift(maff->p[i]);
2869                 if (!maff->p[i])
2870                         goto error;
2871         }
2872
2873         return maff;
2874 error:
2875         if (ls)
2876                 isl_local_space_free(*ls);
2877         return isl_multi_aff_free(maff);
2878 }
2879
2880
2881 /* Extract an isl_pw_aff corresponding to output dimension "pos" of "pma".
2882  */
2883 __isl_give isl_pw_aff *isl_pw_multi_aff_get_pw_aff(
2884         __isl_keep isl_pw_multi_aff *pma, int pos)
2885 {
2886         int i;
2887         int n_out;
2888         isl_space *space;
2889         isl_pw_aff *pa;
2890
2891         if (!pma)
2892                 return NULL;
2893
2894         n_out = isl_pw_multi_aff_dim(pma, isl_dim_out);
2895         if (pos < 0 || pos >= n_out)
2896                 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
2897                         "index out of bounds", return NULL);
2898
2899         space = isl_pw_multi_aff_get_space(pma);
2900         space = isl_space_drop_dims(space, isl_dim_out,
2901                                     pos + 1, n_out - pos - 1);
2902         space = isl_space_drop_dims(space, isl_dim_out, 0, pos);
2903
2904         pa = isl_pw_aff_alloc_size(space, pma->n);
2905         for (i = 0; i < pma->n; ++i) {
2906                 isl_aff *aff;
2907                 aff = isl_multi_aff_get_aff(pma->p[i].maff, pos);
2908                 pa = isl_pw_aff_add_piece(pa, isl_set_copy(pma->p[i].set), aff);
2909         }
2910
2911         return pa;
2912 }
2913
2914 /* Return an isl_pw_multi_aff with the given "set" as domain and
2915  * an unnamed zero-dimensional range.
2916  */
2917 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_domain(
2918         __isl_take isl_set *set)
2919 {
2920         isl_multi_aff *ma;
2921         isl_space *space;
2922
2923         space = isl_set_get_space(set);
2924         space = isl_space_from_domain(space);
2925         ma = isl_multi_aff_zero(space);
2926         return isl_pw_multi_aff_alloc(set, ma);
2927 }
2928
2929 /* Add an isl_pw_multi_aff with the given "set" as domain and
2930  * an unnamed zero-dimensional range to *user.
2931  */
2932 static int add_pw_multi_aff_from_domain(__isl_take isl_set *set, void *user)
2933 {
2934         isl_union_pw_multi_aff **upma = user;
2935         isl_pw_multi_aff *pma;
2936
2937         pma = isl_pw_multi_aff_from_domain(set);
2938         *upma = isl_union_pw_multi_aff_add_pw_multi_aff(*upma, pma);
2939
2940         return 0;
2941 }
2942
2943 /* Return an isl_union_pw_multi_aff with the given "uset" as domain and
2944  * an unnamed zero-dimensional range.
2945  */
2946 __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_from_domain(
2947         __isl_take isl_union_set *uset)
2948 {
2949         isl_space *space;
2950         isl_union_pw_multi_aff *upma;
2951
2952         if (!uset)
2953                 return NULL;
2954
2955         space = isl_union_set_get_space(uset);
2956         upma = isl_union_pw_multi_aff_empty(space);
2957
2958         if (isl_union_set_foreach_set(uset,
2959                                     &add_pw_multi_aff_from_domain, &upma) < 0)
2960                 goto error;
2961
2962         isl_union_set_free(uset);
2963         return upma;
2964 error:
2965         isl_union_set_free(uset);
2966         isl_union_pw_multi_aff_free(upma);
2967         return NULL;
2968 }
2969
2970 /* Convert "pma" to an isl_map and add it to *umap.
2971  */
2972 static int map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma, void *user)
2973 {
2974         isl_union_map **umap = user;
2975         isl_map *map;
2976
2977         map = isl_map_from_pw_multi_aff(pma);
2978         *umap = isl_union_map_add_map(*umap, map);
2979
2980         return 0;
2981 }
2982
2983 /* Construct a union map mapping the domain of the union
2984  * piecewise multi-affine expression to its range, with each dimension
2985  * in the range equated to the corresponding affine expression on its cell.
2986  */
2987 __isl_give isl_union_map *isl_union_map_from_union_pw_multi_aff(
2988         __isl_take isl_union_pw_multi_aff *upma)
2989 {
2990         isl_space *space;
2991         isl_union_map *umap;
2992
2993         if (!upma)
2994                 return NULL;
2995
2996         space = isl_union_pw_multi_aff_get_space(upma);
2997         umap = isl_union_map_empty(space);
2998
2999         if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma,
3000                                         &map_from_pw_multi_aff, &umap) < 0)
3001                 goto error;
3002
3003         isl_union_pw_multi_aff_free(upma);
3004         return umap;
3005 error:
3006         isl_union_pw_multi_aff_free(upma);
3007         isl_union_map_free(umap);
3008         return NULL;
3009 }
3010
3011 /* Local data for bin_entry and the callback "fn".
3012  */
3013 struct isl_union_pw_multi_aff_bin_data {
3014         isl_union_pw_multi_aff *upma2;
3015         isl_union_pw_multi_aff *res;
3016         isl_pw_multi_aff *pma;
3017         int (*fn)(void **entry, void *user);
3018 };
3019
3020 /* Given an isl_pw_multi_aff from upma1, store it in data->pma
3021  * and call data->fn for each isl_pw_multi_aff in data->upma2.
3022  */
3023 static int bin_entry(void **entry, void *user)
3024 {
3025         struct isl_union_pw_multi_aff_bin_data *data = user;
3026         isl_pw_multi_aff *pma = *entry;
3027
3028         data->pma = pma;
3029         if (isl_hash_table_foreach(data->upma2->dim->ctx, &data->upma2->table,
3030                                    data->fn, data) < 0)
3031                 return -1;
3032
3033         return 0;
3034 }
3035
3036 /* Call "fn" on each pair of isl_pw_multi_affs in "upma1" and "upma2".
3037  * The isl_pw_multi_aff from upma1 is stored in data->pma (where data is
3038  * passed as user field) and the isl_pw_multi_aff from upma2 is available
3039  * as *entry.  The callback should adjust data->res if desired.
3040  */
3041 static __isl_give isl_union_pw_multi_aff *bin_op(
3042         __isl_take isl_union_pw_multi_aff *upma1,
3043         __isl_take isl_union_pw_multi_aff *upma2,
3044         int (*fn)(void **entry, void *user))
3045 {
3046         isl_space *space;
3047         struct isl_union_pw_multi_aff_bin_data data = { NULL, NULL, NULL, fn };
3048
3049         space = isl_union_pw_multi_aff_get_space(upma2);
3050         upma1 = isl_union_pw_multi_aff_align_params(upma1, space);
3051         space = isl_union_pw_multi_aff_get_space(upma1);
3052         upma2 = isl_union_pw_multi_aff_align_params(upma2, space);
3053
3054         if (!upma1 || !upma2)
3055                 goto error;
3056
3057         data.upma2 = upma2;
3058         data.res = isl_union_pw_multi_aff_alloc(isl_space_copy(upma1->dim),
3059                                        upma1->table.n);
3060         if (isl_hash_table_foreach(upma1->dim->ctx, &upma1->table,
3061                                    &bin_entry, &data) < 0)
3062                 goto error;
3063
3064         isl_union_pw_multi_aff_free(upma1);
3065         isl_union_pw_multi_aff_free(upma2);
3066         return data.res;
3067 error:
3068         isl_union_pw_multi_aff_free(upma1);
3069         isl_union_pw_multi_aff_free(upma2);
3070         isl_union_pw_multi_aff_free(data.res);
3071         return NULL;
3072 }
3073
3074 /* Given two isl_multi_affs A -> B and C -> D,
3075  * construct an isl_multi_aff (A * C) -> (B, D).
3076  */
3077 __isl_give isl_multi_aff *isl_multi_aff_flat_range_product(
3078         __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2)
3079 {
3080         int i, n1, n2;
3081         isl_aff *aff;
3082         isl_space *space;
3083         isl_multi_aff *res;
3084
3085         if (!ma1 || !ma2)
3086                 goto error;
3087
3088         space = isl_space_range_product(isl_multi_aff_get_space(ma1),
3089                                         isl_multi_aff_get_space(ma2));
3090         space = isl_space_flatten_range(space);
3091         res = isl_multi_aff_alloc(space);
3092
3093         n1 = isl_multi_aff_dim(ma1, isl_dim_out);
3094         n2 = isl_multi_aff_dim(ma2, isl_dim_out);
3095
3096         for (i = 0; i < n1; ++i) {
3097                 aff = isl_multi_aff_get_aff(ma1, i);
3098                 res = isl_multi_aff_set_aff(res, i, aff);
3099         }
3100
3101         for (i = 0; i < n2; ++i) {
3102                 aff = isl_multi_aff_get_aff(ma2, i);
3103                 res = isl_multi_aff_set_aff(res, n1 + i, aff);
3104         }
3105
3106         isl_multi_aff_free(ma1);
3107         isl_multi_aff_free(ma2);
3108         return res;
3109 error:
3110         isl_multi_aff_free(ma1);
3111         isl_multi_aff_free(ma2);
3112         return NULL;
3113 }
3114
3115 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
3116  * construct an isl_pw_multi_aff (A * C) -> (B, D).
3117  */
3118 static __isl_give isl_pw_multi_aff *pw_multi_aff_flat_range_product(
3119         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
3120 {
3121         isl_space *space;
3122
3123         space = isl_space_range_product(isl_pw_multi_aff_get_space(pma1),
3124                                         isl_pw_multi_aff_get_space(pma2));
3125         space = isl_space_flatten_range(space);
3126         return isl_pw_multi_aff_on_shared_domain_in(pma1, pma2, space,
3127                                             &isl_multi_aff_flat_range_product);
3128 }
3129
3130 /* Given two isl_pw_multi_affs A -> B and C -> D,
3131  * construct an isl_pw_multi_aff (A * C) -> (B, D).
3132  */
3133 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_flat_range_product(
3134         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
3135 {
3136         return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
3137                                             &pw_multi_aff_flat_range_product);
3138 }
3139
3140 /* If data->pma and *entry have the same domain space, then compute
3141  * their flat range product and the result to data->res.
3142  */
3143 static int flat_range_product_entry(void **entry, void *user)
3144 {
3145         struct isl_union_pw_multi_aff_bin_data *data = user;
3146         isl_pw_multi_aff *pma2 = *entry;
3147
3148         if (!isl_space_tuple_match(data->pma->dim, isl_dim_in,
3149                                  pma2->dim, isl_dim_in))
3150                 return 0;
3151
3152         pma2 = isl_pw_multi_aff_flat_range_product(
3153                                         isl_pw_multi_aff_copy(data->pma),
3154                                         isl_pw_multi_aff_copy(pma2));
3155
3156         data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res, pma2);
3157
3158         return 0;
3159 }
3160
3161 /* Given two isl_union_pw_multi_affs A -> B and C -> D,
3162  * construct an isl_union_pw_multi_aff (A * C) -> (B, D).
3163  */
3164 __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_flat_range_product(
3165         __isl_take isl_union_pw_multi_aff *upma1,
3166         __isl_take isl_union_pw_multi_aff *upma2)
3167 {
3168         return bin_op(upma1, upma2, &flat_range_product_entry);
3169 }