isl_aff.c

   1 /*
   2  * Copyright 2011      INRIA Saclay
   3  * Copyright 2011      Sven Verdoolaege
   4  *
   5  * Use of this software is governed by the GNU LGPLv2.1 license
   6  *
   7  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   8  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   9  * 91893 Orsay, France
  10  */
  11
  12 #include <isl_ctx_private.h>
  13 #include <isl_map_private.h>
  14 #include <isl_aff_private.h>
  15 #include <isl_space_private.h>
  16 #include <isl_local_space_private.h>
  17 #include <isl_mat_private.h>
  18 #include <isl_list_private.h>
  19 #include <isl/constraint.h>
  20 #include <isl/seq.h>
  21 #include <isl/set.h>
  22
  23 __isl_give isl_aff *isl_aff_alloc_vec(__isl_take isl_local_space *ls,
  24         __isl_take isl_vec *v)
  25 {
  26         isl_aff *aff;
  27
  28         if (!ls || !v)
  29                 goto error;
  30
  31         aff = isl_calloc_type(v->ctx, struct isl_aff);
  32         if (!aff)
  33                 goto error;
  34
  35         aff->ref = 1;
  36         aff->ls = ls;
  37         aff->v = v;
  38
  39         return aff;
  40 error:
  41         isl_local_space_free(ls);
  42         isl_vec_free(v);
  43         return NULL;
  44 }
  45
  46 __isl_give isl_aff *isl_aff_alloc(__isl_take isl_local_space *ls)
  47 {
  48         isl_ctx *ctx;
  49         isl_vec *v;
  50         unsigned total;
  51
  52         if (!ls)
  53                 return NULL;
  54
  55         ctx = isl_local_space_get_ctx(ls);
  56         if (!isl_local_space_divs_known(ls))
  57                 isl_die(ctx, isl_error_invalid, "local space has unknown divs",
  58                         goto error);
  59         if (!isl_local_space_is_set(ls))
  60                 isl_die(ctx, isl_error_invalid,
  61                         "domain of affine expression should be a set",
  62                         goto error);
  63
  64         total = isl_local_space_dim(ls, isl_dim_all);
  65         v = isl_vec_alloc(ctx, 1 + 1 + total);
  66         return isl_aff_alloc_vec(ls, v);
  67 error:
  68         isl_local_space_free(ls);
  69         return NULL;
  70 }
  71
  72 __isl_give isl_aff *isl_aff_zero_on_domain(__isl_take isl_local_space *ls)
  73 {
  74         isl_aff *aff;
  75
  76         aff = isl_aff_alloc(ls);
  77         if (!aff)
  78                 return NULL;
  79
  80         isl_int_set_si(aff->v->el[0], 1);
  81         isl_seq_clr(aff->v->el + 1, aff->v->size - 1);
  82
  83         return aff;
  84 }
  85
  86 __isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff)
  87 {
  88         if (!aff)
  89                 return NULL;
  90
  91         aff->ref++;
  92         return aff;
  93 }
  94
  95 __isl_give isl_aff *isl_aff_dup(__isl_keep isl_aff *aff)
  96 {
  97         if (!aff)
  98                 return NULL;
  99
 100         return isl_aff_alloc_vec(isl_local_space_copy(aff->ls),
 101                                  isl_vec_copy(aff->v));
 102 }
 103
 104 __isl_give isl_aff *isl_aff_cow(__isl_take isl_aff *aff)
 105 {
 106         if (!aff)
 107                 return NULL;
 108
 109         if (aff->ref == 1)
 110                 return aff;
 111         aff->ref--;
 112         return isl_aff_dup(aff);
 113 }
 114
 115 void *isl_aff_free(__isl_take isl_aff *aff)
 116 {
 117         if (!aff)
 118                 return NULL;
 119
 120         if (--aff->ref > 0)
 121                 return NULL;
 122
 123         isl_local_space_free(aff->ls);
 124         isl_vec_free(aff->v);
 125
 126         free(aff);
 127
 128         return NULL;
 129 }
 130
 131 isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff)
 132 {
 133         return aff ? isl_local_space_get_ctx(aff->ls) : NULL;
 134 }
 135
 136 /* Externally, an isl_aff has a map space, but internally, the
 137  * ls field corresponds to the domain of that space.
 138  */
 139 int isl_aff_dim(__isl_keep isl_aff *aff, enum isl_dim_type type)
 140 {
 141         if (!aff)
 142                 return 0;
 143         if (type == isl_dim_out)
 144                 return 1;
 145         if (type == isl_dim_in)
 146                 type = isl_dim_set;
 147         return isl_local_space_dim(aff->ls, type);
 148 }
 149
 150 __isl_give isl_space *isl_aff_get_domain_space(__isl_keep isl_aff *aff)
 151 {
 152         return aff ? isl_local_space_get_space(aff->ls) : NULL;
 153 }
 154
 155 __isl_give isl_space *isl_aff_get_space(__isl_keep isl_aff *aff)
 156 {
 157         isl_space *space;
 158         if (!aff)
 159                 return NULL;
 160         space = isl_local_space_get_space(aff->ls);
 161         space = isl_space_from_domain(space);
 162         space = isl_space_add_dims(space, isl_dim_out, 1);
 163         return space;
 164 }
 165
 166 __isl_give isl_local_space *isl_aff_get_domain_local_space(
 167         __isl_keep isl_aff *aff)
 168 {
 169         return aff ? isl_local_space_copy(aff->ls) : NULL;
 170 }
 171
 172 __isl_give isl_local_space *isl_aff_get_local_space(__isl_keep isl_aff *aff)
 173 {
 174         isl_local_space *ls;
 175         if (!aff)
 176                 return NULL;
 177         ls = isl_local_space_copy(aff->ls);
 178         ls = isl_local_space_from_domain(ls);
 179         ls = isl_local_space_add_dims(ls, isl_dim_out, 1);
 180         return ls;
 181 }
 182
 183 /* Externally, an isl_aff has a map space, but internally, the
 184  * ls field corresponds to the domain of that space.
 185  */
 186 const char *isl_aff_get_dim_name(__isl_keep isl_aff *aff,
 187         enum isl_dim_type type, unsigned pos)
 188 {
 189         if (!aff)
 190                 return NULL;
 191         if (type == isl_dim_out)
 192                 return NULL;
 193         if (type == isl_dim_in)
 194                 type = isl_dim_set;
 195         return isl_local_space_get_dim_name(aff->ls, type, pos);
 196 }
 197
 198 __isl_give isl_aff *isl_aff_reset_domain_space(__isl_take isl_aff *aff,
 199         __isl_take isl_space *dim)
 200 {
 201         aff = isl_aff_cow(aff);
 202         if (!aff || !dim)
 203                 goto error;
 204
 205         aff->ls = isl_local_space_reset_space(aff->ls, dim);
 206         if (!aff->ls)
 207                 return isl_aff_free(aff);
 208
 209         return aff;
 210 error:
 211         isl_aff_free(aff);
 212         isl_space_free(dim);
 213         return NULL;
 214 }
 215
 216 /* Reset the space of "aff".  This function is called from isl_pw_templ.c
 217  * and doesn't know if the space of an element object is represented
 218  * directly or through its domain.  It therefore passes along both.
 219  */
 220 __isl_give isl_aff *isl_aff_reset_space_and_domain(__isl_take isl_aff *aff,
 221         __isl_take isl_space *space, __isl_take isl_space *domain)
 222 {
 223         isl_space_free(space);
 224         return isl_aff_reset_domain_space(aff, domain);
 225 }
 226
 227 /* Reorder the coefficients of the affine expression based
 228  * on the given reodering.
 229  * The reordering r is assumed to have been extended with the local
 230  * variables.
 231  */
 232 static __isl_give isl_vec *vec_reorder(__isl_take isl_vec *vec,
 233         __isl_take isl_reordering *r, int n_div)
 234 {
 235         isl_vec *res;
 236         int i;
 237
 238         if (!vec || !r)
 239                 goto error;
 240
 241         res = isl_vec_alloc(vec->ctx,
 242                             2 + isl_space_dim(r->dim, isl_dim_all) + n_div);
 243         isl_seq_cpy(res->el, vec->el, 2);
 244         isl_seq_clr(res->el + 2, res->size - 2);
 245         for (i = 0; i < r->len; ++i)
 246                 isl_int_set(res->el[2 + r->pos[i]], vec->el[2 + i]);
 247
 248         isl_reordering_free(r);
 249         isl_vec_free(vec);
 250         return res;
 251 error:
 252         isl_vec_free(vec);
 253         isl_reordering_free(r);
 254         return NULL;
 255 }
 256
 257 /* Reorder the dimensions of the domain of "aff" according
 258  * to the given reordering.
 259  */
 260 __isl_give isl_aff *isl_aff_realign_domain(__isl_take isl_aff *aff,
 261         __isl_take isl_reordering *r)
 262 {
 263         aff = isl_aff_cow(aff);
 264         if (!aff)
 265                 goto error;
 266
 267         r = isl_reordering_extend(r, aff->ls->div->n_row);
 268         aff->v = vec_reorder(aff->v, isl_reordering_copy(r),
 269                                 aff->ls->div->n_row);
 270         aff->ls = isl_local_space_realign(aff->ls, r);
 271
 272         if (!aff->v || !aff->ls)
 273                 return isl_aff_free(aff);
 274
 275         return aff;
 276 error:
 277         isl_aff_free(aff);
 278         isl_reordering_free(r);
 279         return NULL;
 280 }
 281
 282 int isl_aff_plain_is_zero(__isl_keep isl_aff *aff)
 283 {
 284         if (!aff)
 285                 return -1;
 286
 287         return isl_seq_first_non_zero(aff->v->el + 1, aff->v->size - 1) < 0;
 288 }
 289
 290 int isl_aff_plain_is_equal(__isl_keep isl_aff *aff1, __isl_keep isl_aff *aff2)
 291 {
 292         int equal;
 293
 294         if (!aff1 || !aff2)
 295                 return -1;
 296
 297         equal = isl_local_space_is_equal(aff1->ls, aff2->ls);
 298         if (equal < 0 || !equal)
 299                 return equal;
 300
 301         return isl_vec_is_equal(aff1->v, aff2->v);
 302 }
 303
 304 int isl_aff_get_denominator(__isl_keep isl_aff *aff, isl_int *v)
 305 {
 306         if (!aff)
 307                 return -1;
 308         isl_int_set(*v, aff->v->el[0]);
 309         return 0;
 310 }
 311
 312 int isl_aff_get_constant(__isl_keep isl_aff *aff, isl_int *v)
 313 {
 314         if (!aff)
 315                 return -1;
 316         isl_int_set(*v, aff->v->el[1]);
 317         return 0;
 318 }
 319
 320 int isl_aff_get_coefficient(__isl_keep isl_aff *aff,
 321         enum isl_dim_type type, int pos, isl_int *v)
 322 {
 323         if (!aff)
 324                 return -1;
 325
 326         if (type == isl_dim_out)
 327                 isl_die(aff->v->ctx, isl_error_invalid,
 328                         "output/set dimension does not have a coefficient",
 329                         return -1);
 330         if (type == isl_dim_in)
 331                 type = isl_dim_set;
 332
 333         if (pos >= isl_local_space_dim(aff->ls, type))
 334                 isl_die(aff->v->ctx, isl_error_invalid,
 335                         "position out of bounds", return -1);
 336
 337         pos += isl_local_space_offset(aff->ls, type);
 338         isl_int_set(*v, aff->v->el[1 + pos]);
 339
 340         return 0;
 341 }
 342
 343 __isl_give isl_aff *isl_aff_set_denominator(__isl_take isl_aff *aff, isl_int v)
 344 {
 345         aff = isl_aff_cow(aff);
 346         if (!aff)
 347                 return NULL;
 348
 349         aff->v = isl_vec_cow(aff->v);
 350         if (!aff->v)
 351                 return isl_aff_free(aff);
 352
 353         isl_int_set(aff->v->el[0], v);
 354
 355         return aff;
 356 }
 357
 358 __isl_give isl_aff *isl_aff_set_constant(__isl_take isl_aff *aff, isl_int v)
 359 {
 360         aff = isl_aff_cow(aff);
 361         if (!aff)
 362                 return NULL;
 363
 364         aff->v = isl_vec_cow(aff->v);
 365         if (!aff->v)
 366                 return isl_aff_free(aff);
 367
 368         isl_int_set(aff->v->el[1], v);
 369
 370         return aff;
 371 }
 372
 373 __isl_give isl_aff *isl_aff_add_constant(__isl_take isl_aff *aff, isl_int v)
 374 {
 375         if (isl_int_is_zero(v))
 376                 return aff;
 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_addmul(aff->v->el[1], aff->v->el[0], v);
 387
 388         return aff;
 389 }
 390
 391 __isl_give isl_aff *isl_aff_add_constant_si(__isl_take isl_aff *aff, int v)
 392 {
 393         isl_int t;
 394
 395         isl_int_init(t);
 396         isl_int_set_si(t, v);
 397         aff = isl_aff_add_constant(aff, t);
 398         isl_int_clear(t);
 399
 400         return aff;
 401 }
 402
 403 __isl_give isl_aff *isl_aff_set_constant_si(__isl_take isl_aff *aff, int v)
 404 {
 405         aff = isl_aff_cow(aff);
 406         if (!aff)
 407                 return NULL;
 408
 409         aff->v = isl_vec_cow(aff->v);
 410         if (!aff->v)
 411                 return isl_aff_free(aff);
 412
 413         isl_int_set_si(aff->v->el[1], v);
 414
 415         return aff;
 416 }
 417
 418 __isl_give isl_aff *isl_aff_set_coefficient(__isl_take isl_aff *aff,
 419         enum isl_dim_type type, int pos, isl_int v)
 420 {
 421         if (!aff)
 422                 return NULL;
 423
 424         if (type == isl_dim_out)
 425                 isl_die(aff->v->ctx, isl_error_invalid,
 426                         "output/set dimension does not have a coefficient",
 427                         return isl_aff_free(aff));
 428         if (type == isl_dim_in)
 429                 type = isl_dim_set;
 430
 431         if (pos >= isl_local_space_dim(aff->ls, type))
 432                 isl_die(aff->v->ctx, isl_error_invalid,
 433                         "position out of bounds", return isl_aff_free(aff));
 434
 435         aff = isl_aff_cow(aff);
 436         if (!aff)
 437                 return NULL;
 438
 439         aff->v = isl_vec_cow(aff->v);
 440         if (!aff->v)
 441                 return isl_aff_free(aff);
 442
 443         pos += isl_local_space_offset(aff->ls, type);
 444         isl_int_set(aff->v->el[1 + pos], v);
 445
 446         return aff;
 447 }
 448
 449 __isl_give isl_aff *isl_aff_set_coefficient_si(__isl_take isl_aff *aff,
 450         enum isl_dim_type type, int pos, int v)
 451 {
 452         if (!aff)
 453                 return NULL;
 454
 455         if (type == isl_dim_out)
 456                 isl_die(aff->v->ctx, isl_error_invalid,
 457                         "output/set dimension does not have a coefficient",
 458                         return isl_aff_free(aff));
 459         if (type == isl_dim_in)
 460                 type = isl_dim_set;
 461
 462         if (pos >= isl_local_space_dim(aff->ls, type))
 463                 isl_die(aff->v->ctx, isl_error_invalid,
 464                         "position out of bounds", return isl_aff_free(aff));
 465
 466         aff = isl_aff_cow(aff);
 467         if (!aff)
 468                 return NULL;
 469
 470         aff->v = isl_vec_cow(aff->v);
 471         if (!aff->v)
 472                 return isl_aff_free(aff);
 473
 474         pos += isl_local_space_offset(aff->ls, type);
 475         isl_int_set_si(aff->v->el[1 + pos], v);
 476
 477         return aff;
 478 }
 479
 480 __isl_give isl_aff *isl_aff_add_coefficient(__isl_take isl_aff *aff,
 481         enum isl_dim_type type, int pos, isl_int v)
 482 {
 483         if (!aff)
 484                 return NULL;
 485
 486         if (type == isl_dim_out)
 487                 isl_die(aff->v->ctx, isl_error_invalid,
 488                         "output/set dimension does not have a coefficient",
 489                         return isl_aff_free(aff));
 490         if (type == isl_dim_in)
 491                 type = isl_dim_set;
 492
 493         if (pos >= isl_local_space_dim(aff->ls, type))
 494                 isl_die(aff->v->ctx, isl_error_invalid,
 495                         "position out of bounds", return isl_aff_free(aff));
 496
 497         aff = isl_aff_cow(aff);
 498         if (!aff)
 499                 return NULL;
 500
 501         aff->v = isl_vec_cow(aff->v);
 502         if (!aff->v)
 503                 return isl_aff_free(aff);
 504
 505         pos += isl_local_space_offset(aff->ls, type);
 506         isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v);
 507
 508         return aff;
 509 }
 510
 511 __isl_give isl_aff *isl_aff_add_coefficient_si(__isl_take isl_aff *aff,
 512         enum isl_dim_type type, int pos, int v)
 513 {
 514         isl_int t;
 515
 516         isl_int_init(t);
 517         isl_int_set_si(t, v);
 518         aff = isl_aff_add_coefficient(aff, type, pos, t);
 519         isl_int_clear(t);
 520
 521         return aff;
 522 }
 523
 524 __isl_give isl_aff *isl_aff_get_div(__isl_keep isl_aff *aff, int pos)
 525 {
 526         if (!aff)
 527                 return NULL;
 528
 529         return isl_local_space_get_div(aff->ls, pos);
 530 }
 531
 532 __isl_give isl_aff *isl_aff_neg(__isl_take isl_aff *aff)
 533 {
 534         aff = isl_aff_cow(aff);
 535         if (!aff)
 536                 return NULL;
 537         aff->v = isl_vec_cow(aff->v);
 538         if (!aff->v)
 539                 return isl_aff_free(aff);
 540
 541         isl_seq_neg(aff->v->el + 1, aff->v->el + 1, aff->v->size - 1);
 542
 543         return aff;
 544 }
 545
 546 /* Given f, return floor(f).
 547  * If f is an integer expression, then just return f.
 548  * Otherwise, if f = g/m, write g = q m + r,
 549  * create a new div d = [r/m] and return the expression q + d.
 550  * The coefficients in r are taken to lie between -m/2 and m/2.
 551  */
 552 __isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff)
 553 {
 554         int i;
 555         int size;
 556         isl_ctx *ctx;
 557         isl_vec *div;
 558
 559         if (!aff)
 560                 return NULL;
 561
 562         if (isl_int_is_one(aff->v->el[0]))
 563                 return aff;
 564
 565         aff = isl_aff_cow(aff);
 566         if (!aff)
 567                 return NULL;
 568
 569         aff->v = isl_vec_cow(aff->v);
 570         div = isl_vec_copy(aff->v);
 571         div = isl_vec_cow(div);
 572         if (!div)
 573                 return isl_aff_free(aff);
 574
 575         ctx = isl_aff_get_ctx(aff);
 576         isl_int_fdiv_q(aff->v->el[0], aff->v->el[0], ctx->two);
 577         for (i = 1; i < aff->v->size; ++i) {
 578                 isl_int_fdiv_r(div->el[i], div->el[i], div->el[0]);
 579                 isl_int_fdiv_q(aff->v->el[i], aff->v->el[i], div->el[0]);
 580                 if (isl_int_gt(div->el[i], aff->v->el[0])) {
 581                         isl_int_sub(div->el[i], div->el[i], div->el[0]);
 582                         isl_int_add_ui(aff->v->el[i], aff->v->el[i], 1);
 583                 }
 584         }
 585
 586         aff->ls = isl_local_space_add_div(aff->ls, div);
 587         if (!aff->ls)
 588                 return isl_aff_free(aff);
 589
 590         size = aff->v->size;
 591         aff->v = isl_vec_extend(aff->v, size + 1);
 592         if (!aff->v)
 593                 return isl_aff_free(aff);
 594         isl_int_set_si(aff->v->el[0], 1);
 595         isl_int_set_si(aff->v->el[size], 1);
 596
 597         return aff;
 598 }
 599
 600 /* Compute
 601  *
 602  *      aff mod m = aff - m * floor(aff/m)
 603  */
 604 __isl_give isl_aff *isl_aff_mod(__isl_take isl_aff *aff, isl_int m)
 605 {
 606         isl_aff *res;
 607
 608         res = isl_aff_copy(aff);
 609         aff = isl_aff_scale_down(aff, m);
 610         aff = isl_aff_floor(aff);
 611         aff = isl_aff_scale(aff, m);
 612         res = isl_aff_sub(res, aff);
 613
 614         return res;
 615 }
 616
 617 /* Compute
 618  *
 619  *      pwaff mod m = pwaff - m * floor(pwaff/m)
 620  */
 621 __isl_give isl_pw_aff *isl_pw_aff_mod(__isl_take isl_pw_aff *pwaff, isl_int m)
 622 {
 623         isl_pw_aff *res;
 624
 625         res = isl_pw_aff_copy(pwaff);
 626         pwaff = isl_pw_aff_scale_down(pwaff, m);
 627         pwaff = isl_pw_aff_floor(pwaff);
 628         pwaff = isl_pw_aff_scale(pwaff, m);
 629         res = isl_pw_aff_sub(res, pwaff);
 630
 631         return res;
 632 }
 633
 634 /* Given f, return ceil(f).
 635  * If f is an integer expression, then just return f.
 636  * Otherwise, create a new div d = [-f] and return the expression -d.
 637  */
 638 __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff)
 639 {
 640         if (!aff)
 641                 return NULL;
 642
 643         if (isl_int_is_one(aff->v->el[0]))
 644                 return aff;
 645
 646         aff = isl_aff_neg(aff);
 647         aff = isl_aff_floor(aff);
 648         aff = isl_aff_neg(aff);
 649
 650         return aff;
 651 }
 652
 653 /* Apply the expansion computed by isl_merge_divs.
 654  * The expansion itself is given by "exp" while the resulting
 655  * list of divs is given by "div".
 656  */
 657 __isl_give isl_aff *isl_aff_expand_divs( __isl_take isl_aff *aff,
 658         __isl_take isl_mat *div, int *exp)
 659 {
 660         int i, j;
 661         int old_n_div;
 662         int new_n_div;
 663         int offset;
 664
 665         aff = isl_aff_cow(aff);
 666         if (!aff || !div)
 667                 goto error;
 668
 669         old_n_div = isl_local_space_dim(aff->ls, isl_dim_div);
 670         new_n_div = isl_mat_rows(div);
 671         if (new_n_div < old_n_div)
 672                 isl_die(isl_mat_get_ctx(div), isl_error_invalid,
 673                         "not an expansion", goto error);
 674
 675         aff->v = isl_vec_extend(aff->v, aff->v->size + new_n_div - old_n_div);
 676         if (!aff->v)
 677                 goto error;
 678
 679         offset = 1 + isl_local_space_offset(aff->ls, isl_dim_div);
 680         j = old_n_div - 1;
 681         for (i = new_n_div - 1; i >= 0; --i) {
 682                 if (j >= 0 && exp[j] == i) {
 683                         if (i != j)
 684                                 isl_int_swap(aff->v->el[offset + i],
 685                                              aff->v->el[offset + j]);
 686                         j--;
 687                 } else
 688                         isl_int_set_si(aff->v->el[offset + i], 0);
 689         }
 690
 691         aff->ls = isl_local_space_replace_divs(aff->ls, isl_mat_copy(div));
 692         if (!aff->ls)
 693                 goto error;
 694         isl_mat_free(div);
 695         return aff;
 696 error:
 697         isl_aff_free(aff);
 698         isl_mat_free(div);
 699         return NULL;
 700 }
 701
 702 /* Add two affine expressions that live in the same local space.
 703  */
 704 static __isl_give isl_aff *add_expanded(__isl_take isl_aff *aff1,
 705         __isl_take isl_aff *aff2)
 706 {
 707         isl_int gcd, f;
 708
 709         aff1 = isl_aff_cow(aff1);
 710         if (!aff1 || !aff2)
 711                 goto error;
 712
 713         aff1->v = isl_vec_cow(aff1->v);
 714         if (!aff1->v)
 715                 goto error;
 716
 717         isl_int_init(gcd);
 718         isl_int_init(f);
 719         isl_int_gcd(gcd, aff1->v->el[0], aff2->v->el[0]);
 720         isl_int_divexact(f, aff2->v->el[0], gcd);
 721         isl_seq_scale(aff1->v->el + 1, aff1->v->el + 1, f, aff1->v->size - 1);
 722         isl_int_divexact(f, aff1->v->el[0], gcd);
 723         isl_seq_addmul(aff1->v->el + 1, f, aff2->v->el + 1, aff1->v->size - 1);
 724         isl_int_divexact(f, aff2->v->el[0], gcd);
 725         isl_int_mul(aff1->v->el[0], aff1->v->el[0], f);
 726         isl_int_clear(f);
 727         isl_int_clear(gcd);
 728
 729         isl_aff_free(aff2);
 730         return aff1;
 731 error:
 732         isl_aff_free(aff1);
 733         isl_aff_free(aff2);
 734         return NULL;
 735 }
 736
 737 __isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
 738         __isl_take isl_aff *aff2)
 739 {
 740         isl_ctx *ctx;
 741         int *exp1 = NULL;
 742         int *exp2 = NULL;
 743         isl_mat *div;
 744
 745         if (!aff1 || !aff2)
 746                 goto error;
 747
 748         ctx = isl_aff_get_ctx(aff1);
 749         if (!isl_space_is_equal(aff1->ls->dim, aff2->ls->dim))
 750                 isl_die(ctx, isl_error_invalid,
 751                         "spaces don't match", goto error);
 752
 753         if (aff1->ls->div->n_row == 0 && aff2->ls->div->n_row == 0)
 754                 return add_expanded(aff1, aff2);
 755
 756         exp1 = isl_alloc_array(ctx, int, aff1->ls->div->n_row);
 757         exp2 = isl_alloc_array(ctx, int, aff2->ls->div->n_row);
 758         if (!exp1 || !exp2)
 759                 goto error;
 760
 761         div = isl_merge_divs(aff1->ls->div, aff2->ls->div, exp1, exp2);
 762         aff1 = isl_aff_expand_divs(aff1, isl_mat_copy(div), exp1);
 763         aff2 = isl_aff_expand_divs(aff2, div, exp2);
 764         free(exp1);
 765         free(exp2);
 766
 767         return add_expanded(aff1, aff2);
 768 error:
 769         free(exp1);
 770         free(exp2);
 771         isl_aff_free(aff1);
 772         isl_aff_free(aff2);
 773         return NULL;
 774 }
 775
 776 __isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
 777         __isl_take isl_aff *aff2)
 778 {
 779         return isl_aff_add(aff1, isl_aff_neg(aff2));
 780 }
 781
 782 __isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f)
 783 {
 784         isl_int gcd;
 785
 786         if (isl_int_is_one(f))
 787                 return aff;
 788
 789         aff = isl_aff_cow(aff);
 790         if (!aff)
 791                 return NULL;
 792         aff->v = isl_vec_cow(aff->v);
 793         if (!aff->v)
 794                 return isl_aff_free(aff);
 795
 796         isl_int_init(gcd);
 797         isl_int_gcd(gcd, aff->v->el[0], f);
 798         isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd);
 799         isl_int_divexact(gcd, f, gcd);
 800         isl_seq_scale(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
 801         isl_int_clear(gcd);
 802
 803         return aff;
 804 }
 805
 806 __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f)
 807 {
 808         isl_int gcd;
 809
 810         if (isl_int_is_one(f))
 811                 return aff;
 812
 813         aff = isl_aff_cow(aff);
 814         if (!aff)
 815                 return NULL;
 816         aff->v = isl_vec_cow(aff->v);
 817         if (!aff->v)
 818                 return isl_aff_free(aff);
 819
 820         isl_int_init(gcd);
 821         isl_seq_gcd(aff->v->el + 1, aff->v->size - 1, &gcd);
 822         isl_int_gcd(gcd, gcd, f);
 823         isl_seq_scale_down(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
 824         isl_int_divexact(gcd, f, gcd);
 825         isl_int_mul(aff->v->el[0], aff->v->el[0], gcd);
 826         isl_int_clear(gcd);
 827
 828         return aff;
 829 }
 830
 831 __isl_give isl_aff *isl_aff_scale_down_ui(__isl_take isl_aff *aff, unsigned f)
 832 {
 833         isl_int v;
 834
 835         if (f == 1)
 836                 return aff;
 837
 838         isl_int_init(v);
 839         isl_int_set_ui(v, f);
 840         aff = isl_aff_scale_down(aff, v);
 841         isl_int_clear(v);
 842
 843         return aff;
 844 }
 845
 846 __isl_give isl_aff *isl_aff_set_dim_name(__isl_take isl_aff *aff,
 847         enum isl_dim_type type, unsigned pos, const char *s)
 848 {
 849         aff = isl_aff_cow(aff);
 850         if (!aff)
 851                 return NULL;
 852         if (type == isl_dim_out)
 853                 isl_die(aff->v->ctx, isl_error_invalid,
 854                         "cannot set name of output/set dimension",
 855                         return isl_aff_free(aff));
 856         if (type == isl_dim_in)
 857                 type = isl_dim_set;
 858         aff->ls = isl_local_space_set_dim_name(aff->ls, type, pos, s);
 859         if (!aff->ls)
 860                 return isl_aff_free(aff);
 861
 862         return aff;
 863 }
 864
 865 __isl_give isl_aff *isl_aff_set_dim_id(__isl_take isl_aff *aff,
 866         enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
 867 {
 868         aff = isl_aff_cow(aff);
 869         if (!aff)
 870                 return isl_id_free(id);
 871         if (type == isl_dim_out)
 872                 isl_die(aff->v->ctx, isl_error_invalid,
 873                         "cannot set name of output/set dimension",
 874                         goto error);
 875         if (type == isl_dim_in)
 876                 type = isl_dim_set;
 877         aff->ls = isl_local_space_set_dim_id(aff->ls, type, pos, id);
 878         if (!aff->ls)
 879                 return isl_aff_free(aff);
 880
 881         return aff;
 882 error:
 883         isl_id_free(id);
 884         isl_aff_free(aff);
 885         return NULL;
 886 }
 887
 888 /* Exploit the equalities in "eq" to simplify the affine expression
 889  * and the expressions of the integer divisions in the local space.
 890  * The integer divisions in this local space are assumed to appear
 891  * as regular dimensions in "eq".
 892  */
 893 static __isl_give isl_aff *isl_aff_substitute_equalities_lifted(
 894         __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
 895 {
 896         int i, j;
 897         unsigned total;
 898         unsigned n_div;
 899
 900         if (!eq)
 901                 goto error;
 902         if (eq->n_eq == 0) {
 903                 isl_basic_set_free(eq);
 904                 return aff;
 905         }
 906
 907         aff = isl_aff_cow(aff);
 908         if (!aff)
 909                 goto error;
 910
 911         aff->ls = isl_local_space_substitute_equalities(aff->ls,
 912                                                         isl_basic_set_copy(eq));
 913         if (!aff->ls)
 914                 goto error;
 915
 916         total = 1 + isl_space_dim(eq->dim, isl_dim_all);
 917         n_div = eq->n_div;
 918         for (i = 0; i < eq->n_eq; ++i) {
 919                 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
 920                 if (j < 0 || j == 0 || j >= total)
 921                         continue;
 922
 923                 isl_seq_elim(aff->v->el + 1, eq->eq[i], j, total,
 924                                 &aff->v->el[0]);
 925         }
 926
 927         isl_basic_set_free(eq);
 928         return aff;
 929 error:
 930         isl_basic_set_free(eq);
 931         isl_aff_free(aff);
 932         return NULL;
 933 }
 934
 935 /* Exploit the equalities in "eq" to simplify the affine expression
 936  * and the expressions of the integer divisions in the local space.
 937  */
 938 static __isl_give isl_aff *isl_aff_substitute_equalities(
 939         __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
 940 {
 941         int n_div;
 942
 943         if (!aff || !eq)
 944                 goto error;
 945         n_div = isl_local_space_dim(aff->ls, isl_dim_div);
 946         if (n_div > 0)
 947                 eq = isl_basic_set_add(eq, isl_dim_set, n_div);
 948         return isl_aff_substitute_equalities_lifted(aff, eq);
 949 error:
 950         isl_basic_set_free(eq);
 951         isl_aff_free(aff);
 952         return NULL;
 953 }
 954
 955 /* Look for equalities among the variables shared by context and aff
 956  * and the integer divisions of aff, if any.
 957  * The equalities are then used to eliminate coefficients and/or integer
 958  * divisions from aff.
 959  */
 960 __isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff,
 961         __isl_take isl_set *context)
 962 {
 963         isl_basic_set *hull;
 964         int n_div;
 965
 966         if (!aff)
 967                 goto error;
 968         n_div = isl_local_space_dim(aff->ls, isl_dim_div);
 969         if (n_div > 0) {
 970                 isl_basic_set *bset;
 971                 isl_local_space *ls;
 972                 context = isl_set_add_dims(context, isl_dim_set, n_div);
 973                 ls = isl_aff_get_domain_local_space(aff);
 974                 bset = isl_basic_set_from_local_space(ls);
 975                 bset = isl_basic_set_lift(bset);
 976                 bset = isl_basic_set_flatten(bset);
 977                 context = isl_set_intersect(context,
 978                                             isl_set_from_basic_set(bset));
 979         }
 980
 981         hull = isl_set_affine_hull(context);
 982         return isl_aff_substitute_equalities_lifted(aff, hull);
 983 error:
 984         isl_aff_free(aff);
 985         isl_set_free(context);
 986         return NULL;
 987 }
 988
 989 /* Return a basic set containing those elements in the space
 990  * of aff where it is non-negative.
 991  */
 992 __isl_give isl_basic_set *isl_aff_nonneg_basic_set(__isl_take isl_aff *aff)
 993 {
 994         isl_constraint *ineq;
 995
 996         ineq = isl_inequality_from_aff(aff);
 997
 998         return isl_basic_set_from_constraint(ineq);
 999 }
1000
1001 /* Return a basic set containing those elements in the space
1002  * of aff where it is zero.
1003  */
1004 __isl_give isl_basic_set *isl_aff_zero_basic_set(__isl_take isl_aff *aff)
1005 {
1006         isl_constraint *ineq;
1007
1008         ineq = isl_equality_from_aff(aff);
1009
1010         return isl_basic_set_from_constraint(ineq);
1011 }
1012
1013 /* Return a basic set containing those elements in the shared space
1014  * of aff1 and aff2 where aff1 is greater than or equal to aff2.
1015  */
1016 __isl_give isl_basic_set *isl_aff_ge_basic_set(__isl_take isl_aff *aff1,
1017         __isl_take isl_aff *aff2)
1018 {
1019         aff1 = isl_aff_sub(aff1, aff2);
1020
1021         return isl_aff_nonneg_basic_set(aff1);
1022 }
1023
1024 /* Return a basic set containing those elements in the shared space
1025  * of aff1 and aff2 where aff1 is smaller than or equal to aff2.
1026  */
1027 __isl_give isl_basic_set *isl_aff_le_basic_set(__isl_take isl_aff *aff1,
1028         __isl_take isl_aff *aff2)
1029 {
1030         return isl_aff_ge_basic_set(aff2, aff1);
1031 }
1032
1033 __isl_give isl_aff *isl_aff_add_on_domain(__isl_keep isl_set *dom,
1034         __isl_take isl_aff *aff1, __isl_take isl_aff *aff2)
1035 {
1036         aff1 = isl_aff_add(aff1, aff2);
1037         aff1 = isl_aff_gist(aff1, isl_set_copy(dom));
1038         return aff1;
1039 }
1040
1041 int isl_aff_is_empty(__isl_keep isl_aff *aff)
1042 {
1043         if (!aff)
1044                 return -1;
1045
1046         return 0;
1047 }
1048
1049 /* Check whether the given affine expression has non-zero coefficient
1050  * for any dimension in the given range or if any of these dimensions
1051  * appear with non-zero coefficients in any of the integer divisions
1052  * involved in the affine expression.
1053  */
1054 int isl_aff_involves_dims(__isl_keep isl_aff *aff,
1055         enum isl_dim_type type, unsigned first, unsigned n)
1056 {
1057         int i;
1058         isl_ctx *ctx;
1059         int *active = NULL;
1060         int involves = 0;
1061
1062         if (!aff)
1063                 return -1;
1064         if (n == 0)
1065                 return 0;
1066
1067         ctx = isl_aff_get_ctx(aff);
1068         if (first + n > isl_aff_dim(aff, type))
1069                 isl_die(ctx, isl_error_invalid,
1070                         "range out of bounds", return -1);
1071
1072         active = isl_local_space_get_active(aff->ls, aff->v->el + 2);
1073         if (!active)
1074                 goto error;
1075
1076         first += isl_local_space_offset(aff->ls, type) - 1;
1077         for (i = 0; i < n; ++i)
1078                 if (active[first + i]) {
1079                         involves = 1;
1080                         break;
1081                 }
1082
1083         free(active);
1084
1085         return involves;
1086 error:
1087         free(active);
1088         return -1;
1089 }
1090
1091 __isl_give isl_aff *isl_aff_drop_dims(__isl_take isl_aff *aff,
1092         enum isl_dim_type type, unsigned first, unsigned n)
1093 {
1094         isl_ctx *ctx;
1095
1096         if (!aff)
1097                 return NULL;
1098         if (type == isl_dim_out)
1099                 isl_die(aff->v->ctx, isl_error_invalid,
1100                         "cannot drop output/set dimension",
1101                         return isl_aff_free(aff));
1102         if (type == isl_dim_in)
1103                 type = isl_dim_set;
1104         if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
1105                 return aff;
1106
1107         ctx = isl_aff_get_ctx(aff);
1108         if (first + n > isl_local_space_dim(aff->ls, type))
1109                 isl_die(ctx, isl_error_invalid, "range out of bounds",
1110                         return isl_aff_free(aff));
1111
1112         aff = isl_aff_cow(aff);
1113         if (!aff)
1114                 return NULL;
1115
1116         aff->ls = isl_local_space_drop_dims(aff->ls, type, first, n);
1117         if (!aff->ls)
1118                 return isl_aff_free(aff);
1119
1120         first += 1 + isl_local_space_offset(aff->ls, type);
1121         aff->v = isl_vec_drop_els(aff->v, first, n);
1122         if (!aff->v)
1123                 return isl_aff_free(aff);
1124
1125         return aff;
1126 }
1127
1128 __isl_give isl_aff *isl_aff_insert_dims(__isl_take isl_aff *aff,
1129         enum isl_dim_type type, unsigned first, unsigned n)
1130 {
1131         isl_ctx *ctx;
1132
1133         if (!aff)
1134                 return NULL;
1135         if (type == isl_dim_out)
1136                 isl_die(aff->v->ctx, isl_error_invalid,
1137                         "cannot insert output/set dimensions",
1138                         return isl_aff_free(aff));
1139         if (type == isl_dim_in)
1140                 type = isl_dim_set;
1141         if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
1142                 return aff;
1143
1144         ctx = isl_aff_get_ctx(aff);
1145         if (first > isl_local_space_dim(aff->ls, type))
1146                 isl_die(ctx, isl_error_invalid, "position out of bounds",
1147                         return isl_aff_free(aff));
1148
1149         aff = isl_aff_cow(aff);
1150         if (!aff)
1151                 return NULL;
1152
1153         aff->ls = isl_local_space_insert_dims(aff->ls, type, first, n);
1154         if (!aff->ls)
1155                 return isl_aff_free(aff);
1156
1157         first += 1 + isl_local_space_offset(aff->ls, type);
1158         aff->v = isl_vec_insert_zero_els(aff->v, first, n);
1159         if (!aff->v)
1160                 return isl_aff_free(aff);
1161
1162         return aff;
1163 }
1164
1165 __isl_give isl_aff *isl_aff_add_dims(__isl_take isl_aff *aff,
1166         enum isl_dim_type type, unsigned n)
1167 {
1168         unsigned pos;
1169
1170         pos = isl_aff_dim(aff, type);
1171
1172         return isl_aff_insert_dims(aff, type, pos, n);
1173 }
1174
1175 __isl_give isl_pw_aff *isl_pw_aff_add_dims(__isl_take isl_pw_aff *pwaff,
1176         enum isl_dim_type type, unsigned n)
1177 {
1178         unsigned pos;
1179
1180         pos = isl_pw_aff_dim(pwaff, type);
1181
1182         return isl_pw_aff_insert_dims(pwaff, type, pos, n);
1183 }
1184
1185 __isl_give isl_pw_aff *isl_pw_aff_from_aff(__isl_take isl_aff *aff)
1186 {
1187         isl_set *dom = isl_set_universe(isl_aff_get_domain_space(aff));
1188         return isl_pw_aff_alloc(dom, aff);
1189 }
1190
1191 #undef PW
1192 #define PW isl_pw_aff
1193 #undef EL
1194 #define EL isl_aff
1195 #undef EL_IS_ZERO
1196 #define EL_IS_ZERO is_empty
1197 #undef ZERO
1198 #define ZERO empty
1199 #undef IS_ZERO
1200 #define IS_ZERO is_empty
1201 #undef FIELD
1202 #define FIELD aff
1203
1204 #define NO_EVAL
1205 #define NO_OPT
1206 #define NO_MOVE_DIMS
1207 #define NO_LIFT
1208 #define NO_MORPH
1209
1210 #include <isl_pw_templ.c>
1211
1212 static __isl_give isl_set *align_params_pw_pw_set_and(
1213         __isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2,
1214         __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1215                                     __isl_take isl_pw_aff *pwaff2))
1216 {
1217         if (!pwaff1 || !pwaff2)
1218                 goto error;
1219         if (isl_space_match(pwaff1->dim, isl_dim_param,
1220                           pwaff2->dim, isl_dim_param))
1221                 return fn(pwaff1, pwaff2);
1222         if (!isl_space_has_named_params(pwaff1->dim) ||
1223             !isl_space_has_named_params(pwaff2->dim))
1224                 isl_die(isl_pw_aff_get_ctx(pwaff1), isl_error_invalid,
1225                         "unaligned unnamed parameters", goto error);
1226         pwaff1 = isl_pw_aff_align_params(pwaff1, isl_pw_aff_get_space(pwaff2));
1227         pwaff2 = isl_pw_aff_align_params(pwaff2, isl_pw_aff_get_space(pwaff1));
1228         return fn(pwaff1, pwaff2);
1229 error:
1230         isl_pw_aff_free(pwaff1);
1231         isl_pw_aff_free(pwaff2);
1232         return NULL;
1233 }
1234
1235 /* Compute a piecewise quasi-affine expression with a domain that
1236  * is the union of those of pwaff1 and pwaff2 and such that on each
1237  * cell, the quasi-affine expression is the better (according to cmp)
1238  * of those of pwaff1 and pwaff2.  If only one of pwaff1 or pwaff2
1239  * is defined on a given cell, then the associated expression
1240  * is the defined one.
1241  */
1242 static __isl_give isl_pw_aff *pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1243         __isl_take isl_pw_aff *pwaff2,
1244         __isl_give isl_basic_set *(*cmp)(__isl_take isl_aff *aff1,
1245                                         __isl_take isl_aff *aff2))
1246 {
1247         int i, j, n;
1248         isl_pw_aff *res;
1249         isl_ctx *ctx;
1250         isl_set *set;
1251
1252         if (!pwaff1 || !pwaff2)
1253                 goto error;
1254
1255         ctx = isl_space_get_ctx(pwaff1->dim);
1256         if (!isl_space_is_equal(pwaff1->dim, pwaff2->dim))
1257                 isl_die(ctx, isl_error_invalid,
1258                         "arguments should live in same space", goto error);
1259
1260         if (isl_pw_aff_is_empty(pwaff1)) {
1261                 isl_pw_aff_free(pwaff1);
1262                 return pwaff2;
1263         }
1264
1265         if (isl_pw_aff_is_empty(pwaff2)) {
1266                 isl_pw_aff_free(pwaff2);
1267                 return pwaff1;
1268         }
1269
1270         n = 2 * (pwaff1->n + 1) * (pwaff2->n + 1);
1271         res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n);
1272
1273         for (i = 0; i < pwaff1->n; ++i) {
1274                 set = isl_set_copy(pwaff1->p[i].set);
1275                 for (j = 0; j < pwaff2->n; ++j) {
1276                         struct isl_set *common;
1277                         isl_set *better;
1278
1279                         common = isl_set_intersect(
1280                                         isl_set_copy(pwaff1->p[i].set),
1281                                         isl_set_copy(pwaff2->p[j].set));
1282                         better = isl_set_from_basic_set(cmp(
1283                                         isl_aff_copy(pwaff2->p[j].aff),
1284                                         isl_aff_copy(pwaff1->p[i].aff)));
1285                         better = isl_set_intersect(common, better);
1286                         if (isl_set_plain_is_empty(better)) {
1287                                 isl_set_free(better);
1288                                 continue;
1289                         }
1290                         set = isl_set_subtract(set, isl_set_copy(better));
1291
1292                         res = isl_pw_aff_add_piece(res, better,
1293                                                 isl_aff_copy(pwaff2->p[j].aff));
1294                 }
1295                 res = isl_pw_aff_add_piece(res, set,
1296                                                 isl_aff_copy(pwaff1->p[i].aff));
1297         }
1298
1299         for (j = 0; j < pwaff2->n; ++j) {
1300                 set = isl_set_copy(pwaff2->p[j].set);
1301                 for (i = 0; i < pwaff1->n; ++i)
1302                         set = isl_set_subtract(set,
1303                                         isl_set_copy(pwaff1->p[i].set));
1304                 res = isl_pw_aff_add_piece(res, set,
1305                                                 isl_aff_copy(pwaff2->p[j].aff));
1306         }
1307
1308         isl_pw_aff_free(pwaff1);
1309         isl_pw_aff_free(pwaff2);
1310
1311         return res;
1312 error:
1313         isl_pw_aff_free(pwaff1);
1314         isl_pw_aff_free(pwaff2);
1315         return NULL;
1316 }
1317
1318 /* Compute a piecewise quasi-affine expression with a domain that
1319  * is the union of those of pwaff1 and pwaff2 and such that on each
1320  * cell, the quasi-affine expression is the maximum of those of pwaff1
1321  * and pwaff2.  If only one of pwaff1 or pwaff2 is defined on a given
1322  * cell, then the associated expression is the defined one.
1323  */
1324 static __isl_give isl_pw_aff *pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1325         __isl_take isl_pw_aff *pwaff2)
1326 {
1327         return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_ge_basic_set);
1328 }
1329
1330 __isl_give isl_pw_aff *isl_pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1331         __isl_take isl_pw_aff *pwaff2)
1332 {
1333         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2,
1334                                                         &pw_aff_union_max);
1335 }
1336
1337 /* Compute a piecewise quasi-affine expression with a domain that
1338  * is the union of those of pwaff1 and pwaff2 and such that on each
1339  * cell, the quasi-affine expression is the minimum of those of pwaff1
1340  * and pwaff2.  If only one of pwaff1 or pwaff2 is defined on a given
1341  * cell, then the associated expression is the defined one.
1342  */
1343 static __isl_give isl_pw_aff *pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1344         __isl_take isl_pw_aff *pwaff2)
1345 {
1346         return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_le_basic_set);
1347 }
1348
1349 __isl_give isl_pw_aff *isl_pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1350         __isl_take isl_pw_aff *pwaff2)
1351 {
1352         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2,
1353                                                         &pw_aff_union_min);
1354 }
1355
1356 __isl_give isl_pw_aff *isl_pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1357         __isl_take isl_pw_aff *pwaff2, int max)
1358 {
1359         if (max)
1360                 return isl_pw_aff_union_max(pwaff1, pwaff2);
1361         else
1362                 return isl_pw_aff_union_min(pwaff1, pwaff2);
1363 }
1364
1365 /* Construct a map with as domain the domain of pwaff and
1366  * one-dimensional range corresponding to the affine expressions.
1367  */
1368 static __isl_give isl_map *map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1369 {
1370         int i;
1371         isl_space *dim;
1372         isl_map *map;
1373
1374         if (!pwaff)
1375                 return NULL;
1376
1377         dim = isl_pw_aff_get_space(pwaff);
1378         map = isl_map_empty(dim);
1379
1380         for (i = 0; i < pwaff->n; ++i) {
1381                 isl_basic_map *bmap;
1382                 isl_map *map_i;
1383
1384                 bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
1385                 map_i = isl_map_from_basic_map(bmap);
1386                 map_i = isl_map_intersect_domain(map_i,
1387                                                 isl_set_copy(pwaff->p[i].set));
1388                 map = isl_map_union_disjoint(map, map_i);
1389         }
1390
1391         isl_pw_aff_free(pwaff);
1392
1393         return map;
1394 }
1395
1396 /* Construct a map with as domain the domain of pwaff and
1397  * one-dimensional range corresponding to the affine expressions.
1398  */
1399 __isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1400 {
1401         if (isl_space_is_set(pwaff->dim))
1402                 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1403                         "space of input is not a map",
1404                         return isl_pw_aff_free(pwaff));
1405         return map_from_pw_aff(pwaff);
1406 }
1407
1408 /* Construct a one-dimensional set with as parameter domain
1409  * the domain of pwaff and the single set dimension
1410  * corresponding to the affine expressions.
1411  */
1412 __isl_give isl_set *isl_set_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1413 {
1414         if (!isl_space_is_set(pwaff->dim))
1415                 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1416                         "space of input is not a set",
1417                         return isl_pw_aff_free(pwaff));
1418         return map_from_pw_aff(pwaff);
1419 }
1420
1421 /* Return a set containing those elements in the domain
1422  * of pwaff where it is non-negative.
1423  */
1424 __isl_give isl_set *isl_pw_aff_nonneg_set(__isl_take isl_pw_aff *pwaff)
1425 {
1426         int i;
1427         isl_set *set;
1428
1429         if (!pwaff)
1430                 return NULL;
1431
1432         set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1433
1434         for (i = 0; i < pwaff->n; ++i) {
1435                 isl_basic_set *bset;
1436                 isl_set *set_i;
1437
1438                 bset = isl_aff_nonneg_basic_set(isl_aff_copy(pwaff->p[i].aff));
1439                 set_i = isl_set_from_basic_set(bset);
1440                 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1441                 set = isl_set_union_disjoint(set, set_i);
1442         }
1443
1444         isl_pw_aff_free(pwaff);
1445
1446         return set;
1447 }
1448
1449 /* Return a set containing those elements in the domain
1450  * of pwaff where it is zero.
1451  */
1452 __isl_give isl_set *isl_pw_aff_zero_set(__isl_take isl_pw_aff *pwaff)
1453 {
1454         int i;
1455         isl_set *set;
1456
1457         if (!pwaff)
1458                 return NULL;
1459
1460         set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1461
1462         for (i = 0; i < pwaff->n; ++i) {
1463                 isl_basic_set *bset;
1464                 isl_set *set_i;
1465
1466                 bset = isl_aff_zero_basic_set(isl_aff_copy(pwaff->p[i].aff));
1467                 set_i = isl_set_from_basic_set(bset);
1468                 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1469                 set = isl_set_union_disjoint(set, set_i);
1470         }
1471
1472         isl_pw_aff_free(pwaff);
1473
1474         return set;
1475 }
1476
1477 /* Return a set containing those elements in the domain
1478  * of pwaff where it is not zero.
1479  */
1480 __isl_give isl_set *isl_pw_aff_non_zero_set(__isl_take isl_pw_aff *pwaff)
1481 {
1482         return isl_set_complement(isl_pw_aff_zero_set(pwaff));
1483 }
1484
1485 /* Return a set containing those elements in the shared domain
1486  * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
1487  *
1488  * We compute the difference on the shared domain and then construct
1489  * the set of values where this difference is non-negative.
1490  * If strict is set, we first subtract 1 from the difference.
1491  * If equal is set, we only return the elements where pwaff1 and pwaff2
1492  * are equal.
1493  */
1494 static __isl_give isl_set *pw_aff_gte_set(__isl_take isl_pw_aff *pwaff1,
1495         __isl_take isl_pw_aff *pwaff2, int strict, int equal)
1496 {
1497         isl_set *set1, *set2;
1498
1499         set1 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff1));
1500         set2 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff2));
1501         set1 = isl_set_intersect(set1, set2);
1502         pwaff1 = isl_pw_aff_intersect_domain(pwaff1, isl_set_copy(set1));
1503         pwaff2 = isl_pw_aff_intersect_domain(pwaff2, isl_set_copy(set1));
1504         pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_neg(pwaff2));
1505
1506         if (strict) {
1507                 isl_space *dim = isl_set_get_space(set1);
1508                 isl_aff *aff;
1509                 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
1510                 aff = isl_aff_add_constant_si(aff, -1);
1511                 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_alloc(set1, aff));
1512         } else
1513                 isl_set_free(set1);
1514
1515         if (equal)
1516                 return isl_pw_aff_zero_set(pwaff1);
1517         return isl_pw_aff_nonneg_set(pwaff1);
1518 }
1519
1520 /* Return a set containing those elements in the shared domain
1521  * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
1522  */
1523 static __isl_give isl_set *pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1524         __isl_take isl_pw_aff *pwaff2)
1525 {
1526         return pw_aff_gte_set(pwaff1, pwaff2, 0, 1);
1527 }
1528
1529 __isl_give isl_set *isl_pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1530         __isl_take isl_pw_aff *pwaff2)
1531 {
1532         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_eq_set);
1533 }
1534
1535 /* Return a set containing those elements in the shared domain
1536  * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
1537  */
1538 static __isl_give isl_set *pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1539         __isl_take isl_pw_aff *pwaff2)
1540 {
1541         return pw_aff_gte_set(pwaff1, pwaff2, 0, 0);
1542 }
1543
1544 __isl_give isl_set *isl_pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1545         __isl_take isl_pw_aff *pwaff2)
1546 {
1547         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ge_set);
1548 }
1549
1550 /* Return a set containing those elements in the shared domain
1551  * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
1552  */
1553 static __isl_give isl_set *pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1554         __isl_take isl_pw_aff *pwaff2)
1555 {
1556         return pw_aff_gte_set(pwaff1, pwaff2, 1, 0);
1557 }
1558
1559 __isl_give isl_set *isl_pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1560         __isl_take isl_pw_aff *pwaff2)
1561 {
1562         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_gt_set);
1563 }
1564
1565 __isl_give isl_set *isl_pw_aff_le_set(__isl_take isl_pw_aff *pwaff1,
1566         __isl_take isl_pw_aff *pwaff2)
1567 {
1568         return isl_pw_aff_ge_set(pwaff2, pwaff1);
1569 }
1570
1571 __isl_give isl_set *isl_pw_aff_lt_set(__isl_take isl_pw_aff *pwaff1,
1572         __isl_take isl_pw_aff *pwaff2)
1573 {
1574         return isl_pw_aff_gt_set(pwaff2, pwaff1);
1575 }
1576
1577 /* Return a set containing those elements in the shared domain
1578  * of the elements of list1 and list2 where each element in list1
1579  * has the relation specified by "fn" with each element in list2.
1580  */
1581 static __isl_give isl_set *pw_aff_list_set(__isl_take isl_pw_aff_list *list1,
1582         __isl_take isl_pw_aff_list *list2,
1583         __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1584                                     __isl_take isl_pw_aff *pwaff2))
1585 {
1586         int i, j;
1587         isl_ctx *ctx;
1588         isl_set *set;
1589
1590         if (!list1 || !list2)
1591                 goto error;
1592
1593         ctx = isl_pw_aff_list_get_ctx(list1);
1594         if (list1->n < 1 || list2->n < 1)
1595                 isl_die(ctx, isl_error_invalid,
1596                         "list should contain at least one element", goto error);
1597
1598         set = isl_set_universe(isl_pw_aff_get_domain_space(list1->p[0]));
1599         for (i = 0; i < list1->n; ++i)
1600                 for (j = 0; j < list2->n; ++j) {
1601                         isl_set *set_ij;
1602
1603                         set_ij = fn(isl_pw_aff_copy(list1->p[i]),
1604                                     isl_pw_aff_copy(list2->p[j]));
1605                         set = isl_set_intersect(set, set_ij);
1606                 }
1607
1608         isl_pw_aff_list_free(list1);
1609         isl_pw_aff_list_free(list2);
1610         return set;
1611 error:
1612         isl_pw_aff_list_free(list1);
1613         isl_pw_aff_list_free(list2);
1614         return NULL;
1615 }
1616
1617 /* Return a set containing those elements in the shared domain
1618  * of the elements of list1 and list2 where each element in list1
1619  * is equal to each element in list2.
1620  */
1621 __isl_give isl_set *isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list *list1,
1622         __isl_take isl_pw_aff_list *list2)
1623 {
1624         return pw_aff_list_set(list1, list2, &isl_pw_aff_eq_set);
1625 }
1626
1627 __isl_give isl_set *isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list *list1,
1628         __isl_take isl_pw_aff_list *list2)
1629 {
1630         return pw_aff_list_set(list1, list2, &isl_pw_aff_ne_set);
1631 }
1632
1633 /* Return a set containing those elements in the shared domain
1634  * of the elements of list1 and list2 where each element in list1
1635  * is less than or equal to each element in list2.
1636  */
1637 __isl_give isl_set *isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list *list1,
1638         __isl_take isl_pw_aff_list *list2)
1639 {
1640         return pw_aff_list_set(list1, list2, &isl_pw_aff_le_set);
1641 }
1642
1643 __isl_give isl_set *isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list *list1,
1644         __isl_take isl_pw_aff_list *list2)
1645 {
1646         return pw_aff_list_set(list1, list2, &isl_pw_aff_lt_set);
1647 }
1648
1649 __isl_give isl_set *isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list *list1,
1650         __isl_take isl_pw_aff_list *list2)
1651 {
1652         return pw_aff_list_set(list1, list2, &isl_pw_aff_ge_set);
1653 }
1654
1655 __isl_give isl_set *isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list *list1,
1656         __isl_take isl_pw_aff_list *list2)
1657 {
1658         return pw_aff_list_set(list1, list2, &isl_pw_aff_gt_set);
1659 }
1660
1661
1662 /* Return a set containing those elements in the shared domain
1663  * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
1664  */
1665 static __isl_give isl_set *pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1666         __isl_take isl_pw_aff *pwaff2)
1667 {
1668         isl_set *set_lt, *set_gt;
1669
1670         set_lt = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1),
1671                                    isl_pw_aff_copy(pwaff2));
1672         set_gt = isl_pw_aff_gt_set(pwaff1, pwaff2);
1673         return isl_set_union_disjoint(set_lt, set_gt);
1674 }
1675
1676 __isl_give isl_set *isl_pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1677         __isl_take isl_pw_aff *pwaff2)
1678 {
1679         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ne_set);
1680 }
1681
1682 __isl_give isl_pw_aff *isl_pw_aff_scale_down(__isl_take isl_pw_aff *pwaff,
1683         isl_int v)
1684 {
1685         int i;
1686
1687         if (isl_int_is_one(v))
1688                 return pwaff;
1689         if (!isl_int_is_pos(v))
1690                 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1691                         "factor needs to be positive",
1692                         return isl_pw_aff_free(pwaff));
1693         pwaff = isl_pw_aff_cow(pwaff);
1694         if (!pwaff)
1695                 return NULL;
1696         if (pwaff->n == 0)
1697                 return pwaff;
1698
1699         for (i = 0; i < pwaff->n; ++i) {
1700                 pwaff->p[i].aff = isl_aff_scale_down(pwaff->p[i].aff, v);
1701                 if (!pwaff->p[i].aff)
1702                         return isl_pw_aff_free(pwaff);
1703         }
1704
1705         return pwaff;
1706 }
1707
1708 __isl_give isl_pw_aff *isl_pw_aff_floor(__isl_take isl_pw_aff *pwaff)
1709 {
1710         int i;
1711
1712         pwaff = isl_pw_aff_cow(pwaff);
1713         if (!pwaff)
1714                 return NULL;
1715         if (pwaff->n == 0)
1716                 return pwaff;
1717
1718         for (i = 0; i < pwaff->n; ++i) {
1719                 pwaff->p[i].aff = isl_aff_floor(pwaff->p[i].aff);
1720                 if (!pwaff->p[i].aff)
1721                         return isl_pw_aff_free(pwaff);
1722         }
1723
1724         return pwaff;
1725 }
1726
1727 __isl_give isl_pw_aff *isl_pw_aff_ceil(__isl_take isl_pw_aff *pwaff)
1728 {
1729         int i;
1730
1731         pwaff = isl_pw_aff_cow(pwaff);
1732         if (!pwaff)
1733                 return NULL;
1734         if (pwaff->n == 0)
1735                 return pwaff;
1736
1737         for (i = 0; i < pwaff->n; ++i) {
1738                 pwaff->p[i].aff = isl_aff_ceil(pwaff->p[i].aff);
1739                 if (!pwaff->p[i].aff)
1740                         return isl_pw_aff_free(pwaff);
1741         }
1742
1743         return pwaff;
1744 }
1745
1746 /* Return an affine expression that is equal to pwaff_true for elements
1747  * in "cond" and to pwaff_false for elements not in "cond".
1748  * That is, return cond ? pwaff_true : pwaff_false;
1749  */
1750 __isl_give isl_pw_aff *isl_pw_aff_cond(__isl_take isl_set *cond,
1751         __isl_take isl_pw_aff *pwaff_true, __isl_take isl_pw_aff *pwaff_false)
1752 {
1753         isl_set *comp;
1754
1755         comp = isl_set_complement(isl_set_copy(cond));
1756         pwaff_true = isl_pw_aff_intersect_domain(pwaff_true, cond);
1757         pwaff_false = isl_pw_aff_intersect_domain(pwaff_false, comp);
1758
1759         return isl_pw_aff_add_disjoint(pwaff_true, pwaff_false);
1760 }
1761
1762 int isl_aff_is_cst(__isl_keep isl_aff *aff)
1763 {
1764         if (!aff)
1765                 return -1;
1766
1767         return isl_seq_first_non_zero(aff->v->el + 2, aff->v->size - 2) == -1;
1768 }
1769
1770 /* Check whether pwaff is a piecewise constant.
1771  */
1772 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff)
1773 {
1774         int i;
1775
1776         if (!pwaff)
1777                 return -1;
1778
1779         for (i = 0; i < pwaff->n; ++i) {
1780                 int is_cst = isl_aff_is_cst(pwaff->p[i].aff);
1781                 if (is_cst < 0 || !is_cst)
1782                         return is_cst;
1783         }
1784
1785         return 1;
1786 }
1787
1788 __isl_give isl_aff *isl_aff_mul(__isl_take isl_aff *aff1,
1789         __isl_take isl_aff *aff2)
1790 {
1791         if (!isl_aff_is_cst(aff2) && isl_aff_is_cst(aff1))
1792                 return isl_aff_mul(aff2, aff1);
1793
1794         if (!isl_aff_is_cst(aff2))
1795                 isl_die(isl_aff_get_ctx(aff1), isl_error_invalid,
1796                         "at least one affine expression should be constant",
1797                         goto error);
1798
1799         aff1 = isl_aff_cow(aff1);
1800         if (!aff1 || !aff2)
1801                 goto error;
1802
1803         aff1 = isl_aff_scale(aff1, aff2->v->el[1]);
1804         aff1 = isl_aff_scale_down(aff1, aff2->v->el[0]);
1805
1806         isl_aff_free(aff2);
1807         return aff1;
1808 error:
1809         isl_aff_free(aff1);
1810         isl_aff_free(aff2);
1811         return NULL;
1812 }
1813
1814 static __isl_give isl_pw_aff *pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
1815         __isl_take isl_pw_aff *pwaff2)
1816 {
1817         int i, j, n;
1818         isl_pw_aff *res;
1819
1820         if (!pwaff1 || !pwaff2)
1821                 goto error;
1822
1823         n = pwaff1->n * pwaff2->n;
1824         res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n);
1825
1826         for (i = 0; i < pwaff1->n; ++i) {
1827                 for (j = 0; j < pwaff2->n; ++j) {
1828                         isl_set *common;
1829                         isl_aff *prod;
1830                         common = isl_set_intersect(
1831                                         isl_set_copy(pwaff1->p[i].set),
1832                                         isl_set_copy(pwaff2->p[j].set));
1833                         if (isl_set_plain_is_empty(common)) {
1834                                 isl_set_free(common);
1835                                 continue;
1836                         }
1837
1838                         prod = isl_aff_mul(isl_aff_copy(pwaff1->p[i].aff),
1839                                             isl_aff_copy(pwaff2->p[j].aff));
1840
1841                         res = isl_pw_aff_add_piece(res, common, prod);
1842                 }
1843         }
1844
1845         isl_pw_aff_free(pwaff1);
1846         isl_pw_aff_free(pwaff2);
1847         return res;
1848 error:
1849         isl_pw_aff_free(pwaff1);
1850         isl_pw_aff_free(pwaff2);
1851         return NULL;
1852 }
1853
1854 __isl_give isl_pw_aff *isl_pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
1855         __isl_take isl_pw_aff *pwaff2)
1856 {
1857         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_mul);
1858 }
1859
1860 static __isl_give isl_pw_aff *pw_aff_min(__isl_take isl_pw_aff *pwaff1,
1861         __isl_take isl_pw_aff *pwaff2)
1862 {
1863         isl_set *le;
1864
1865         le = isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1),
1866                                 isl_pw_aff_copy(pwaff2));
1867         return isl_pw_aff_cond(le, pwaff1, pwaff2);
1868 }
1869
1870 __isl_give isl_pw_aff *isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1,
1871         __isl_take isl_pw_aff *pwaff2)
1872 {
1873         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_min);
1874 }
1875
1876 static __isl_give isl_pw_aff *pw_aff_max(__isl_take isl_pw_aff *pwaff1,
1877         __isl_take isl_pw_aff *pwaff2)
1878 {
1879         isl_set *le;
1880
1881         le = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1),
1882                                 isl_pw_aff_copy(pwaff2));
1883         return isl_pw_aff_cond(le, pwaff1, pwaff2);
1884 }
1885
1886 __isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1,
1887         __isl_take isl_pw_aff *pwaff2)
1888 {
1889         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_max);
1890 }
1891
1892 static __isl_give isl_pw_aff *pw_aff_list_reduce(
1893         __isl_take isl_pw_aff_list *list,
1894         __isl_give isl_pw_aff *(*fn)(__isl_take isl_pw_aff *pwaff1,
1895                                         __isl_take isl_pw_aff *pwaff2))
1896 {
1897         int i;
1898         isl_ctx *ctx;
1899         isl_pw_aff *res;
1900
1901         if (!list)
1902                 return NULL;
1903
1904         ctx = isl_pw_aff_list_get_ctx(list);
1905         if (list->n < 1)
1906                 isl_die(ctx, isl_error_invalid,
1907                         "list should contain at least one element",
1908                         return isl_pw_aff_list_free(list));
1909
1910         res = isl_pw_aff_copy(list->p[0]);
1911         for (i = 1; i < list->n; ++i)
1912                 res = fn(res, isl_pw_aff_copy(list->p[i]));
1913
1914         isl_pw_aff_list_free(list);
1915         return res;
1916 }
1917
1918 /* Return an isl_pw_aff that maps each element in the intersection of the
1919  * domains of the elements of list to the minimal corresponding affine
1920  * expression.
1921  */
1922 __isl_give isl_pw_aff *isl_pw_aff_list_min(__isl_take isl_pw_aff_list *list)
1923 {
1924         return pw_aff_list_reduce(list, &isl_pw_aff_min);
1925 }
1926
1927 /* Return an isl_pw_aff that maps each element in the intersection of the
1928  * domains of the elements of list to the maximal corresponding affine
1929  * expression.
1930  */
1931 __isl_give isl_pw_aff *isl_pw_aff_list_max(__isl_take isl_pw_aff_list *list)
1932 {
1933         return pw_aff_list_reduce(list, &isl_pw_aff_max);
1934 }
1935
1936 #undef BASE
1937 #define BASE aff
1938
1939 #include <isl_multi_templ.c>
1940
1941 __isl_give isl_multi_aff *isl_multi_aff_add(__isl_take isl_multi_aff *maff1,
1942         __isl_take isl_multi_aff *maff2)
1943 {
1944         int i;
1945         isl_ctx *ctx;
1946
1947         maff1 = isl_multi_aff_cow(maff1);
1948         if (!maff1 || !maff2)
1949                 goto error;
1950
1951         ctx = isl_multi_aff_get_ctx(maff1);
1952         if (!isl_space_is_equal(maff1->space, maff2->space))
1953                 isl_die(ctx, isl_error_invalid,
1954                         "spaces don't match", goto error);
1955
1956         for (i = 0; i < maff1->n; ++i) {
1957                 maff1->p[i] = isl_aff_add(maff1->p[i],
1958                                             isl_aff_copy(maff2->p[i]));
1959                 if (!maff1->p[i])
1960                         goto error;
1961         }
1962
1963         isl_multi_aff_free(maff2);
1964         return maff1;
1965 error:
1966         isl_multi_aff_free(maff1);
1967         isl_multi_aff_free(maff2);
1968         return NULL;
1969 }
1970
1971 /* Exploit the equalities in "eq" to simplify the affine expressions.
1972  */
1973 static __isl_give isl_multi_aff *isl_multi_aff_substitute_equalities(
1974         __isl_take isl_multi_aff *maff, __isl_take isl_basic_set *eq)
1975 {
1976         int i;
1977
1978         maff = isl_multi_aff_cow(maff);
1979         if (!maff || !eq)
1980                 goto error;
1981
1982         for (i = 0; i < maff->n; ++i) {
1983                 maff->p[i] = isl_aff_substitute_equalities(maff->p[i],
1984                                                     isl_basic_set_copy(eq));
1985                 if (!maff->p[i])
1986                         goto error;
1987         }
1988
1989         isl_basic_set_free(eq);
1990         return maff;
1991 error:
1992         isl_basic_set_free(eq);
1993         isl_multi_aff_free(maff);
1994         return NULL;
1995 }
1996
1997 __isl_give isl_multi_aff *isl_multi_aff_scale(__isl_take isl_multi_aff *maff,
1998         isl_int f)
1999 {
2000         int i;
2001
2002         maff = isl_multi_aff_cow(maff);
2003         if (!maff)
2004                 return NULL;
2005
2006         for (i = 0; i < maff->n; ++i) {
2007                 maff->p[i] = isl_aff_scale(maff->p[i], f);
2008                 if (!maff->p[i])
2009                         return isl_multi_aff_free(maff);
2010         }
2011
2012         return maff;
2013 }
2014
2015 __isl_give isl_multi_aff *isl_multi_aff_add_on_domain(__isl_keep isl_set *dom,
2016         __isl_take isl_multi_aff *maff1, __isl_take isl_multi_aff *maff2)
2017 {
2018         maff1 = isl_multi_aff_add(maff1, maff2);
2019         maff1 = isl_multi_aff_gist(maff1, isl_set_copy(dom));
2020         return maff1;
2021 }
2022
2023 int isl_multi_aff_is_empty(__isl_keep isl_multi_aff *maff)
2024 {
2025         if (!maff)
2026                 return -1;
2027
2028         return 0;
2029 }
2030
2031 int isl_multi_aff_plain_is_equal(__isl_keep isl_multi_aff *maff1,
2032         __isl_keep isl_multi_aff *maff2)
2033 {
2034         int i;
2035         int equal;
2036
2037         if (!maff1 || !maff2)
2038                 return -1;
2039         if (maff1->n != maff2->n)
2040                 return 0;
2041         equal = isl_space_is_equal(maff1->space, maff2->space);
2042         if (equal < 0 || !equal)
2043                 return equal;
2044
2045         for (i = 0; i < maff1->n; ++i) {
2046                 equal = isl_aff_plain_is_equal(maff1->p[i], maff2->p[i]);
2047                 if (equal < 0 || !equal)
2048                         return equal;
2049         }
2050
2051         return 1;
2052 }
2053
2054 __isl_give isl_multi_aff *isl_multi_aff_set_dim_name(
2055         __isl_take isl_multi_aff *maff,
2056         enum isl_dim_type type, unsigned pos, const char *s)
2057 {
2058         int i;
2059
2060         maff = isl_multi_aff_cow(maff);
2061         if (!maff)
2062                 return NULL;
2063
2064         maff->space = isl_space_set_dim_name(maff->space, type, pos, s);
2065         if (!maff->space)
2066                 return isl_multi_aff_free(maff);
2067         for (i = 0; i < maff->n; ++i) {
2068                 maff->p[i] = isl_aff_set_dim_name(maff->p[i], type, pos, s);
2069                 if (!maff->p[i])
2070                         return isl_multi_aff_free(maff);
2071         }
2072
2073         return maff;
2074 }
2075
2076 __isl_give isl_multi_aff *isl_multi_aff_drop_dims(__isl_take isl_multi_aff *maff,
2077         enum isl_dim_type type, unsigned first, unsigned n)
2078 {
2079         int i;
2080
2081         maff = isl_multi_aff_cow(maff);
2082         if (!maff)
2083                 return NULL;
2084
2085         maff->space = isl_space_drop_dims(maff->space, type, first, n);
2086         if (!maff->space)
2087                 return isl_multi_aff_free(maff);
2088         for (i = 0; i < maff->n; ++i) {
2089                 maff->p[i] = isl_aff_drop_dims(maff->p[i], type, first, n);
2090                 if (!maff->p[i])
2091                         return isl_multi_aff_free(maff);
2092         }
2093
2094         return maff;
2095 }
2096
2097 #undef PW
2098 #define PW isl_pw_multi_aff
2099 #undef EL
2100 #define EL isl_multi_aff
2101 #undef EL_IS_ZERO
2102 #define EL_IS_ZERO is_empty
2103 #undef ZERO
2104 #define ZERO empty
2105 #undef IS_ZERO
2106 #define IS_ZERO is_empty
2107 #undef FIELD
2108 #define FIELD maff
2109
2110 #define NO_NEG
2111 #define NO_EVAL
2112 #define NO_OPT
2113 #define NO_INVOLVES_DIMS
2114 #define NO_MOVE_DIMS
2115 #define NO_INSERT_DIMS
2116 #define NO_LIFT
2117 #define NO_MORPH
2118
2119 #include <isl_pw_templ.c>
2120
2121 /* Construct a map mapping the domain the piecewise multi-affine expression
2122  * to its range, with each dimension in the range equated to the
2123  * corresponding affine expression on its cell.
2124  */
2125 __isl_give isl_map *isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
2126 {
2127         int i;
2128         isl_map *map;
2129
2130         if (!pma)
2131                 return NULL;
2132
2133         map = isl_map_empty(isl_pw_multi_aff_get_space(pma));
2134
2135         for (i = 0; i < pma->n; ++i) {
2136                 isl_multi_aff *maff;
2137                 isl_basic_map *bmap;
2138                 isl_map *map_i;
2139
2140                 maff = isl_multi_aff_copy(pma->p[i].maff);
2141                 bmap = isl_basic_map_from_multi_aff(maff);
2142                 map_i = isl_map_from_basic_map(bmap);
2143                 map_i = isl_map_intersect_domain(map_i,
2144                                                 isl_set_copy(pma->p[i].set));
2145                 map = isl_map_union_disjoint(map, map_i);
2146         }
2147
2148         isl_pw_multi_aff_free(pma);
2149         return map;
2150 }
2151
2152 __isl_give isl_set *isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
2153 {
2154         if (!isl_space_is_set(pma->dim))
2155                 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
2156                         "isl_pw_multi_aff cannot be converted into an isl_set",
2157                         return isl_pw_multi_aff_free(pma));
2158
2159         return isl_map_from_pw_multi_aff(pma);
2160 }