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 align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_union_max);
1334 }
1335
1336 /* Compute a piecewise quasi-affine expression with a domain that
1337  * is the union of those of pwaff1 and pwaff2 and such that on each
1338  * cell, the quasi-affine expression is the minimum of those of pwaff1
1339  * and pwaff2.  If only one of pwaff1 or pwaff2 is defined on a given
1340  * cell, then the associated expression is the defined one.
1341  */
1342 static __isl_give isl_pw_aff *pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1343         __isl_take isl_pw_aff *pwaff2)
1344 {
1345         return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_le_basic_set);
1346 }
1347
1348 __isl_give isl_pw_aff *isl_pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1349         __isl_take isl_pw_aff *pwaff2)
1350 {
1351         return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_union_min);
1352 }
1353
1354 __isl_give isl_pw_aff *isl_pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1355         __isl_take isl_pw_aff *pwaff2, int max)
1356 {
1357         if (max)
1358                 return isl_pw_aff_union_max(pwaff1, pwaff2);
1359         else
1360                 return isl_pw_aff_union_min(pwaff1, pwaff2);
1361 }
1362
1363 /* Construct a map with as domain the domain of pwaff and
1364  * one-dimensional range corresponding to the affine expressions.
1365  */
1366 static __isl_give isl_map *map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1367 {
1368         int i;
1369         isl_space *dim;
1370         isl_map *map;
1371
1372         if (!pwaff)
1373                 return NULL;
1374
1375         dim = isl_pw_aff_get_space(pwaff);
1376         map = isl_map_empty(dim);
1377
1378         for (i = 0; i < pwaff->n; ++i) {
1379                 isl_basic_map *bmap;
1380                 isl_map *map_i;
1381
1382                 bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
1383                 map_i = isl_map_from_basic_map(bmap);
1384                 map_i = isl_map_intersect_domain(map_i,
1385                                                 isl_set_copy(pwaff->p[i].set));
1386                 map = isl_map_union_disjoint(map, map_i);
1387         }
1388
1389         isl_pw_aff_free(pwaff);
1390
1391         return map;
1392 }
1393
1394 /* Construct a map with as domain the domain of pwaff and
1395  * one-dimensional range corresponding to the affine expressions.
1396  */
1397 __isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1398 {
1399         if (isl_space_is_set(pwaff->dim))
1400                 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1401                         "space of input is not a map",
1402                         return isl_pw_aff_free(pwaff));
1403         return map_from_pw_aff(pwaff);
1404 }
1405
1406 /* Construct a one-dimensional set with as parameter domain
1407  * the domain of pwaff and the single set dimension
1408  * corresponding to the affine expressions.
1409  */
1410 __isl_give isl_set *isl_set_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1411 {
1412         if (!isl_space_is_set(pwaff->dim))
1413                 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1414                         "space of input is not a set",
1415                         return isl_pw_aff_free(pwaff));
1416         return map_from_pw_aff(pwaff);
1417 }
1418
1419 /* Return a set containing those elements in the domain
1420  * of pwaff where it is non-negative.
1421  */
1422 __isl_give isl_set *isl_pw_aff_nonneg_set(__isl_take isl_pw_aff *pwaff)
1423 {
1424         int i;
1425         isl_set *set;
1426
1427         if (!pwaff)
1428                 return NULL;
1429
1430         set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1431
1432         for (i = 0; i < pwaff->n; ++i) {
1433                 isl_basic_set *bset;
1434                 isl_set *set_i;
1435
1436                 bset = isl_aff_nonneg_basic_set(isl_aff_copy(pwaff->p[i].aff));
1437                 set_i = isl_set_from_basic_set(bset);
1438                 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1439                 set = isl_set_union_disjoint(set, set_i);
1440         }
1441
1442         isl_pw_aff_free(pwaff);
1443
1444         return set;
1445 }
1446
1447 /* Return a set containing those elements in the domain
1448  * of pwaff where it is zero.
1449  */
1450 __isl_give isl_set *isl_pw_aff_zero_set(__isl_take isl_pw_aff *pwaff)
1451 {
1452         int i;
1453         isl_set *set;
1454
1455         if (!pwaff)
1456                 return NULL;
1457
1458         set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1459
1460         for (i = 0; i < pwaff->n; ++i) {
1461                 isl_basic_set *bset;
1462                 isl_set *set_i;
1463
1464                 bset = isl_aff_zero_basic_set(isl_aff_copy(pwaff->p[i].aff));
1465                 set_i = isl_set_from_basic_set(bset);
1466                 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1467                 set = isl_set_union_disjoint(set, set_i);
1468         }
1469
1470         isl_pw_aff_free(pwaff);
1471
1472         return set;
1473 }
1474
1475 /* Return a set containing those elements in the domain
1476  * of pwaff where it is not zero.
1477  */
1478 __isl_give isl_set *isl_pw_aff_non_zero_set(__isl_take isl_pw_aff *pwaff)
1479 {
1480         return isl_set_complement(isl_pw_aff_zero_set(pwaff));
1481 }
1482
1483 /* Return a set containing those elements in the shared domain
1484  * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
1485  *
1486  * We compute the difference on the shared domain and then construct
1487  * the set of values where this difference is non-negative.
1488  * If strict is set, we first subtract 1 from the difference.
1489  * If equal is set, we only return the elements where pwaff1 and pwaff2
1490  * are equal.
1491  */
1492 static __isl_give isl_set *pw_aff_gte_set(__isl_take isl_pw_aff *pwaff1,
1493         __isl_take isl_pw_aff *pwaff2, int strict, int equal)
1494 {
1495         isl_set *set1, *set2;
1496
1497         set1 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff1));
1498         set2 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff2));
1499         set1 = isl_set_intersect(set1, set2);
1500         pwaff1 = isl_pw_aff_intersect_domain(pwaff1, isl_set_copy(set1));
1501         pwaff2 = isl_pw_aff_intersect_domain(pwaff2, isl_set_copy(set1));
1502         pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_neg(pwaff2));
1503
1504         if (strict) {
1505                 isl_space *dim = isl_set_get_space(set1);
1506                 isl_aff *aff;
1507                 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
1508                 aff = isl_aff_add_constant_si(aff, -1);
1509                 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_alloc(set1, aff));
1510         } else
1511                 isl_set_free(set1);
1512
1513         if (equal)
1514                 return isl_pw_aff_zero_set(pwaff1);
1515         return isl_pw_aff_nonneg_set(pwaff1);
1516 }
1517
1518 /* Return a set containing those elements in the shared domain
1519  * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
1520  */
1521 static __isl_give isl_set *pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1522         __isl_take isl_pw_aff *pwaff2)
1523 {
1524         return pw_aff_gte_set(pwaff1, pwaff2, 0, 1);
1525 }
1526
1527 __isl_give isl_set *isl_pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1528         __isl_take isl_pw_aff *pwaff2)
1529 {
1530         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_eq_set);
1531 }
1532
1533 /* Return a set containing those elements in the shared domain
1534  * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
1535  */
1536 static __isl_give isl_set *pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1537         __isl_take isl_pw_aff *pwaff2)
1538 {
1539         return pw_aff_gte_set(pwaff1, pwaff2, 0, 0);
1540 }
1541
1542 __isl_give isl_set *isl_pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1543         __isl_take isl_pw_aff *pwaff2)
1544 {
1545         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ge_set);
1546 }
1547
1548 /* Return a set containing those elements in the shared domain
1549  * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
1550  */
1551 static __isl_give isl_set *pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1552         __isl_take isl_pw_aff *pwaff2)
1553 {
1554         return pw_aff_gte_set(pwaff1, pwaff2, 1, 0);
1555 }
1556
1557 __isl_give isl_set *isl_pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1558         __isl_take isl_pw_aff *pwaff2)
1559 {
1560         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_gt_set);
1561 }
1562
1563 __isl_give isl_set *isl_pw_aff_le_set(__isl_take isl_pw_aff *pwaff1,
1564         __isl_take isl_pw_aff *pwaff2)
1565 {
1566         return isl_pw_aff_ge_set(pwaff2, pwaff1);
1567 }
1568
1569 __isl_give isl_set *isl_pw_aff_lt_set(__isl_take isl_pw_aff *pwaff1,
1570         __isl_take isl_pw_aff *pwaff2)
1571 {
1572         return isl_pw_aff_gt_set(pwaff2, pwaff1);
1573 }
1574
1575 /* Return a set containing those elements in the shared domain
1576  * of the elements of list1 and list2 where each element in list1
1577  * has the relation specified by "fn" with each element in list2.
1578  */
1579 static __isl_give isl_set *pw_aff_list_set(__isl_take isl_pw_aff_list *list1,
1580         __isl_take isl_pw_aff_list *list2,
1581         __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1582                                     __isl_take isl_pw_aff *pwaff2))
1583 {
1584         int i, j;
1585         isl_ctx *ctx;
1586         isl_set *set;
1587
1588         if (!list1 || !list2)
1589                 goto error;
1590
1591         ctx = isl_pw_aff_list_get_ctx(list1);
1592         if (list1->n < 1 || list2->n < 1)
1593                 isl_die(ctx, isl_error_invalid,
1594                         "list should contain at least one element", goto error);
1595
1596         set = isl_set_universe(isl_pw_aff_get_domain_space(list1->p[0]));
1597         for (i = 0; i < list1->n; ++i)
1598                 for (j = 0; j < list2->n; ++j) {
1599                         isl_set *set_ij;
1600
1601                         set_ij = fn(isl_pw_aff_copy(list1->p[i]),
1602                                     isl_pw_aff_copy(list2->p[j]));
1603                         set = isl_set_intersect(set, set_ij);
1604                 }
1605
1606         isl_pw_aff_list_free(list1);
1607         isl_pw_aff_list_free(list2);
1608         return set;
1609 error:
1610         isl_pw_aff_list_free(list1);
1611         isl_pw_aff_list_free(list2);
1612         return NULL;
1613 }
1614
1615 /* Return a set containing those elements in the shared domain
1616  * of the elements of list1 and list2 where each element in list1
1617  * is equal to each element in list2.
1618  */
1619 __isl_give isl_set *isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list *list1,
1620         __isl_take isl_pw_aff_list *list2)
1621 {
1622         return pw_aff_list_set(list1, list2, &isl_pw_aff_eq_set);
1623 }
1624
1625 __isl_give isl_set *isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list *list1,
1626         __isl_take isl_pw_aff_list *list2)
1627 {
1628         return pw_aff_list_set(list1, list2, &isl_pw_aff_ne_set);
1629 }
1630
1631 /* Return a set containing those elements in the shared domain
1632  * of the elements of list1 and list2 where each element in list1
1633  * is less than or equal to each element in list2.
1634  */
1635 __isl_give isl_set *isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list *list1,
1636         __isl_take isl_pw_aff_list *list2)
1637 {
1638         return pw_aff_list_set(list1, list2, &isl_pw_aff_le_set);
1639 }
1640
1641 __isl_give isl_set *isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list *list1,
1642         __isl_take isl_pw_aff_list *list2)
1643 {
1644         return pw_aff_list_set(list1, list2, &isl_pw_aff_lt_set);
1645 }
1646
1647 __isl_give isl_set *isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list *list1,
1648         __isl_take isl_pw_aff_list *list2)
1649 {
1650         return pw_aff_list_set(list1, list2, &isl_pw_aff_ge_set);
1651 }
1652
1653 __isl_give isl_set *isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list *list1,
1654         __isl_take isl_pw_aff_list *list2)
1655 {
1656         return pw_aff_list_set(list1, list2, &isl_pw_aff_gt_set);
1657 }
1658
1659
1660 /* Return a set containing those elements in the shared domain
1661  * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
1662  */
1663 static __isl_give isl_set *pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1664         __isl_take isl_pw_aff *pwaff2)
1665 {
1666         isl_set *set_lt, *set_gt;
1667
1668         set_lt = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1),
1669                                    isl_pw_aff_copy(pwaff2));
1670         set_gt = isl_pw_aff_gt_set(pwaff1, pwaff2);
1671         return isl_set_union_disjoint(set_lt, set_gt);
1672 }
1673
1674 __isl_give isl_set *isl_pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1675         __isl_take isl_pw_aff *pwaff2)
1676 {
1677         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ne_set);
1678 }
1679
1680 __isl_give isl_pw_aff *isl_pw_aff_scale_down(__isl_take isl_pw_aff *pwaff,
1681         isl_int v)
1682 {
1683         int i;
1684
1685         if (isl_int_is_one(v))
1686                 return pwaff;
1687         if (!isl_int_is_pos(v))
1688                 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1689                         "factor needs to be positive",
1690                         return isl_pw_aff_free(pwaff));
1691         pwaff = isl_pw_aff_cow(pwaff);
1692         if (!pwaff)
1693                 return NULL;
1694         if (pwaff->n == 0)
1695                 return pwaff;
1696
1697         for (i = 0; i < pwaff->n; ++i) {
1698                 pwaff->p[i].aff = isl_aff_scale_down(pwaff->p[i].aff, v);
1699                 if (!pwaff->p[i].aff)
1700                         return isl_pw_aff_free(pwaff);
1701         }
1702
1703         return pwaff;
1704 }
1705
1706 __isl_give isl_pw_aff *isl_pw_aff_floor(__isl_take isl_pw_aff *pwaff)
1707 {
1708         int i;
1709
1710         pwaff = isl_pw_aff_cow(pwaff);
1711         if (!pwaff)
1712                 return NULL;
1713         if (pwaff->n == 0)
1714                 return pwaff;
1715
1716         for (i = 0; i < pwaff->n; ++i) {
1717                 pwaff->p[i].aff = isl_aff_floor(pwaff->p[i].aff);
1718                 if (!pwaff->p[i].aff)
1719                         return isl_pw_aff_free(pwaff);
1720         }
1721
1722         return pwaff;
1723 }
1724
1725 __isl_give isl_pw_aff *isl_pw_aff_ceil(__isl_take isl_pw_aff *pwaff)
1726 {
1727         int i;
1728
1729         pwaff = isl_pw_aff_cow(pwaff);
1730         if (!pwaff)
1731                 return NULL;
1732         if (pwaff->n == 0)
1733                 return pwaff;
1734
1735         for (i = 0; i < pwaff->n; ++i) {
1736                 pwaff->p[i].aff = isl_aff_ceil(pwaff->p[i].aff);
1737                 if (!pwaff->p[i].aff)
1738                         return isl_pw_aff_free(pwaff);
1739         }
1740
1741         return pwaff;
1742 }
1743
1744 /* Return an affine expression that is equal to pwaff_true for elements
1745  * in "cond" and to pwaff_false for elements not in "cond".
1746  * That is, return cond ? pwaff_true : pwaff_false;
1747  */
1748 __isl_give isl_pw_aff *isl_pw_aff_cond(__isl_take isl_set *cond,
1749         __isl_take isl_pw_aff *pwaff_true, __isl_take isl_pw_aff *pwaff_false)
1750 {
1751         isl_set *comp;
1752
1753         comp = isl_set_complement(isl_set_copy(cond));
1754         pwaff_true = isl_pw_aff_intersect_domain(pwaff_true, cond);
1755         pwaff_false = isl_pw_aff_intersect_domain(pwaff_false, comp);
1756
1757         return isl_pw_aff_add_disjoint(pwaff_true, pwaff_false);
1758 }
1759
1760 int isl_aff_is_cst(__isl_keep isl_aff *aff)
1761 {
1762         if (!aff)
1763                 return -1;
1764
1765         return isl_seq_first_non_zero(aff->v->el + 2, aff->v->size - 2) == -1;
1766 }
1767
1768 /* Check whether pwaff is a piecewise constant.
1769  */
1770 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff)
1771 {
1772         int i;
1773
1774         if (!pwaff)
1775                 return -1;
1776
1777         for (i = 0; i < pwaff->n; ++i) {
1778                 int is_cst = isl_aff_is_cst(pwaff->p[i].aff);
1779                 if (is_cst < 0 || !is_cst)
1780                         return is_cst;
1781         }
1782
1783         return 1;
1784 }
1785
1786 __isl_give isl_aff *isl_aff_mul(__isl_take isl_aff *aff1,
1787         __isl_take isl_aff *aff2)
1788 {
1789         if (!isl_aff_is_cst(aff2) && isl_aff_is_cst(aff1))
1790                 return isl_aff_mul(aff2, aff1);
1791
1792         if (!isl_aff_is_cst(aff2))
1793                 isl_die(isl_aff_get_ctx(aff1), isl_error_invalid,
1794                         "at least one affine expression should be constant",
1795                         goto error);
1796
1797         aff1 = isl_aff_cow(aff1);
1798         if (!aff1 || !aff2)
1799                 goto error;
1800
1801         aff1 = isl_aff_scale(aff1, aff2->v->el[1]);
1802         aff1 = isl_aff_scale_down(aff1, aff2->v->el[0]);
1803
1804         isl_aff_free(aff2);
1805         return aff1;
1806 error:
1807         isl_aff_free(aff1);
1808         isl_aff_free(aff2);
1809         return NULL;
1810 }
1811
1812 static __isl_give isl_pw_aff *pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
1813         __isl_take isl_pw_aff *pwaff2)
1814 {
1815         int i, j, n;
1816         isl_pw_aff *res;
1817
1818         if (!pwaff1 || !pwaff2)
1819                 goto error;
1820
1821         n = pwaff1->n * pwaff2->n;
1822         res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n);
1823
1824         for (i = 0; i < pwaff1->n; ++i) {
1825                 for (j = 0; j < pwaff2->n; ++j) {
1826                         isl_set *common;
1827                         isl_aff *prod;
1828                         common = isl_set_intersect(
1829                                         isl_set_copy(pwaff1->p[i].set),
1830                                         isl_set_copy(pwaff2->p[j].set));
1831                         if (isl_set_plain_is_empty(common)) {
1832                                 isl_set_free(common);
1833                                 continue;
1834                         }
1835
1836                         prod = isl_aff_mul(isl_aff_copy(pwaff1->p[i].aff),
1837                                             isl_aff_copy(pwaff2->p[j].aff));
1838
1839                         res = isl_pw_aff_add_piece(res, common, prod);
1840                 }
1841         }
1842
1843         isl_pw_aff_free(pwaff1);
1844         isl_pw_aff_free(pwaff2);
1845         return res;
1846 error:
1847         isl_pw_aff_free(pwaff1);
1848         isl_pw_aff_free(pwaff2);
1849         return NULL;
1850 }
1851
1852 __isl_give isl_pw_aff *isl_pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
1853         __isl_take isl_pw_aff *pwaff2)
1854 {
1855         return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_mul);
1856 }
1857
1858 static __isl_give isl_pw_aff *pw_aff_min(__isl_take isl_pw_aff *pwaff1,
1859         __isl_take isl_pw_aff *pwaff2)
1860 {
1861         isl_set *le;
1862
1863         le = isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1),
1864                                 isl_pw_aff_copy(pwaff2));
1865         return isl_pw_aff_cond(le, pwaff1, pwaff2);
1866 }
1867
1868 __isl_give isl_pw_aff *isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1,
1869         __isl_take isl_pw_aff *pwaff2)
1870 {
1871         return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_min);
1872 }
1873
1874 static __isl_give isl_pw_aff *pw_aff_max(__isl_take isl_pw_aff *pwaff1,
1875         __isl_take isl_pw_aff *pwaff2)
1876 {
1877         isl_set *le;
1878
1879         le = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1),
1880                                 isl_pw_aff_copy(pwaff2));
1881         return isl_pw_aff_cond(le, pwaff1, pwaff2);
1882 }
1883
1884 __isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1,
1885         __isl_take isl_pw_aff *pwaff2)
1886 {
1887         return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_max);
1888 }
1889
1890 static __isl_give isl_pw_aff *pw_aff_list_reduce(
1891         __isl_take isl_pw_aff_list *list,
1892         __isl_give isl_pw_aff *(*fn)(__isl_take isl_pw_aff *pwaff1,
1893                                         __isl_take isl_pw_aff *pwaff2))
1894 {
1895         int i;
1896         isl_ctx *ctx;
1897         isl_pw_aff *res;
1898
1899         if (!list)
1900                 return NULL;
1901
1902         ctx = isl_pw_aff_list_get_ctx(list);
1903         if (list->n < 1)
1904                 isl_die(ctx, isl_error_invalid,
1905                         "list should contain at least one element",
1906                         return isl_pw_aff_list_free(list));
1907
1908         res = isl_pw_aff_copy(list->p[0]);
1909         for (i = 1; i < list->n; ++i)
1910                 res = fn(res, isl_pw_aff_copy(list->p[i]));
1911
1912         isl_pw_aff_list_free(list);
1913         return res;
1914 }
1915
1916 /* Return an isl_pw_aff that maps each element in the intersection of the
1917  * domains of the elements of list to the minimal corresponding affine
1918  * expression.
1919  */
1920 __isl_give isl_pw_aff *isl_pw_aff_list_min(__isl_take isl_pw_aff_list *list)
1921 {
1922         return pw_aff_list_reduce(list, &isl_pw_aff_min);
1923 }
1924
1925 /* Return an isl_pw_aff that maps each element in the intersection of the
1926  * domains of the elements of list to the maximal corresponding affine
1927  * expression.
1928  */
1929 __isl_give isl_pw_aff *isl_pw_aff_list_max(__isl_take isl_pw_aff_list *list)
1930 {
1931         return pw_aff_list_reduce(list, &isl_pw_aff_max);
1932 }