isl_aff.c

   1 /*
   2  * Copyright 2011      INRIA Saclay
   3  * Copyright 2011      Universiteit Leiden
   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  * and Leiden Institute of Advanced Computer Science,
  11  * Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands
  12  */
  13
  14 #include <isl_ctx_private.h>
  15 #include <isl_map_private.h>
  16 #include <isl_aff_private.h>
  17 #include <isl_dim_private.h>
  18 #include <isl_local_space_private.h>
  19 #include <isl_mat_private.h>
  20 #include <isl_list_private.h>
  21 #include <isl/constraint.h>
  22 #include <isl/seq.h>
  23 #include <isl/set.h>
  24
  25 __isl_give isl_aff *isl_aff_alloc_vec(__isl_take isl_local_space *ls,
  26         __isl_take isl_vec *v)
  27 {
  28         isl_aff *aff;
  29
  30         if (!ls || !v)
  31                 goto error;
  32
  33         aff = isl_calloc_type(v->ctx, struct isl_aff);
  34         if (!aff)
  35                 goto error;
  36
  37         aff->ref = 1;
  38         aff->ls = ls;
  39         aff->v = v;
  40
  41         return aff;
  42 error:
  43         isl_local_space_free(ls);
  44         isl_vec_free(v);
  45         return NULL;
  46 }
  47
  48 __isl_give isl_aff *isl_aff_alloc(__isl_take isl_local_space *ls)
  49 {
  50         isl_ctx *ctx;
  51         isl_vec *v;
  52         unsigned total;
  53
  54         if (!ls)
  55                 return NULL;
  56
  57         ctx = isl_local_space_get_ctx(ls);
  58         if (!isl_local_space_divs_known(ls))
  59                 isl_die(ctx, isl_error_invalid, "local space has unknown divs",
  60                         goto error);
  61
  62         total = isl_local_space_dim(ls, isl_dim_all);
  63         v = isl_vec_alloc(ctx, 1 + 1 + total);
  64         return isl_aff_alloc_vec(ls, v);
  65 error:
  66         isl_local_space_free(ls);
  67         return NULL;
  68 }
  69
  70 __isl_give isl_aff *isl_aff_zero(__isl_take isl_local_space *ls)
  71 {
  72         isl_aff *aff;
  73
  74         aff = isl_aff_alloc(ls);
  75         if (!aff)
  76                 return NULL;
  77
  78         isl_int_set_si(aff->v->el[0], 1);
  79         isl_seq_clr(aff->v->el + 1, aff->v->size - 1);
  80
  81         return aff;
  82 }
  83
  84 __isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff)
  85 {
  86         if (!aff)
  87                 return NULL;
  88
  89         aff->ref++;
  90         return aff;
  91 }
  92
  93 __isl_give isl_aff *isl_aff_dup(__isl_keep isl_aff *aff)
  94 {
  95         if (!aff)
  96                 return NULL;
  97
  98         return isl_aff_alloc_vec(isl_local_space_copy(aff->ls),
  99                                  isl_vec_copy(aff->v));
 100 }
 101
 102 __isl_give isl_aff *isl_aff_cow(__isl_take isl_aff *aff)
 103 {
 104         if (!aff)
 105                 return NULL;
 106
 107         if (aff->ref == 1)
 108                 return aff;
 109         aff->ref--;
 110         return isl_aff_dup(aff);
 111 }
 112
 113 void *isl_aff_free(__isl_take isl_aff *aff)
 114 {
 115         if (!aff)
 116                 return NULL;
 117
 118         if (--aff->ref > 0)
 119                 return NULL;
 120
 121         isl_local_space_free(aff->ls);
 122         isl_vec_free(aff->v);
 123
 124         free(aff);
 125
 126         return NULL;
 127 }
 128
 129 isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff)
 130 {
 131         return aff ? isl_local_space_get_ctx(aff->ls) : NULL;
 132 }
 133
 134 int isl_aff_dim(__isl_keep isl_aff *aff, enum isl_dim_type type)
 135 {
 136         return aff ? isl_local_space_dim(aff->ls, type) : 0;
 137 }
 138
 139 __isl_give isl_dim *isl_aff_get_dim(__isl_keep isl_aff *aff)
 140 {
 141         return aff ? isl_local_space_get_dim(aff->ls) : NULL;
 142 }
 143
 144 __isl_give isl_local_space *isl_aff_get_local_space(__isl_keep isl_aff *aff)
 145 {
 146         return aff ? isl_local_space_copy(aff->ls) : NULL;
 147 }
 148
 149 const char *isl_aff_get_dim_name(__isl_keep isl_aff *aff,
 150         enum isl_dim_type type, unsigned pos)
 151 {
 152         return aff ? isl_local_space_get_dim_name(aff->ls, type, pos) : 0;
 153 }
 154
 155 __isl_give isl_aff *isl_aff_reset_dim(__isl_take isl_aff *aff,
 156         __isl_take isl_dim *dim)
 157 {
 158         aff = isl_aff_cow(aff);
 159         if (!aff || !dim)
 160                 goto error;
 161
 162         aff->ls = isl_local_space_reset_dim(aff->ls, dim);
 163         if (!aff->ls)
 164                 return isl_aff_free(aff);
 165
 166         return aff;
 167 error:
 168         isl_aff_free(aff);
 169         isl_dim_free(dim);
 170         return NULL;
 171 }
 172
 173 /* Reorder the coefficients of the affine expression based
 174  * on the given reodering.
 175  * The reordering r is assumed to have been extended with the local
 176  * variables.
 177  */
 178 static __isl_give isl_vec *vec_reorder(__isl_take isl_vec *vec,
 179         __isl_take isl_reordering *r, int n_div)
 180 {
 181         isl_vec *res;
 182         int i;
 183
 184         if (!vec || !r)
 185                 goto error;
 186
 187         res = isl_vec_alloc(vec->ctx, 2 + isl_dim_total(r->dim) + n_div);
 188         isl_seq_cpy(res->el, vec->el, 2);
 189         isl_seq_clr(res->el + 2, res->size - 2);
 190         for (i = 0; i < r->len; ++i)
 191                 isl_int_set(res->el[2 + r->pos[i]], vec->el[2 + i]);
 192
 193         isl_reordering_free(r);
 194         isl_vec_free(vec);
 195         return res;
 196 error:
 197         isl_vec_free(vec);
 198         isl_reordering_free(r);
 199         return NULL;
 200 }
 201
 202 /* Reorder the dimensions of "aff" according to the given reordering.
 203  */
 204 __isl_give isl_aff *isl_aff_realign(__isl_take isl_aff *aff,
 205         __isl_take isl_reordering *r)
 206 {
 207         aff = isl_aff_cow(aff);
 208         if (!aff)
 209                 goto error;
 210
 211         r = isl_reordering_extend(r, aff->ls->div->n_row);
 212         aff->v = vec_reorder(aff->v, isl_reordering_copy(r),
 213                                 aff->ls->div->n_row);
 214         aff->ls = isl_local_space_realign(aff->ls, r);
 215
 216         if (!aff->v || !aff->ls)
 217                 return isl_aff_free(aff);
 218
 219         return aff;
 220 error:
 221         isl_aff_free(aff);
 222         isl_reordering_free(r);
 223         return NULL;
 224 }
 225
 226 int isl_aff_plain_is_zero(__isl_keep isl_aff *aff)
 227 {
 228         if (!aff)
 229                 return -1;
 230
 231         return isl_seq_first_non_zero(aff->v->el + 1, aff->v->size - 1) < 0;
 232 }
 233
 234 int isl_aff_plain_is_equal(__isl_keep isl_aff *aff1, __isl_keep isl_aff *aff2)
 235 {
 236         int equal;
 237
 238         if (!aff1 || !aff2)
 239                 return -1;
 240
 241         equal = isl_local_space_is_equal(aff1->ls, aff2->ls);
 242         if (equal < 0 || !equal)
 243                 return equal;
 244
 245         return isl_vec_is_equal(aff1->v, aff2->v);
 246 }
 247
 248 int isl_aff_get_denominator(__isl_keep isl_aff *aff, isl_int *v)
 249 {
 250         if (!aff)
 251                 return -1;
 252         isl_int_set(*v, aff->v->el[0]);
 253         return 0;
 254 }
 255
 256 int isl_aff_get_constant(__isl_keep isl_aff *aff, isl_int *v)
 257 {
 258         if (!aff)
 259                 return -1;
 260         isl_int_set(*v, aff->v->el[1]);
 261         return 0;
 262 }
 263
 264 int isl_aff_get_coefficient(__isl_keep isl_aff *aff,
 265         enum isl_dim_type type, int pos, isl_int *v)
 266 {
 267         if (!aff)
 268                 return -1;
 269
 270         if (pos >= isl_local_space_dim(aff->ls, type))
 271                 isl_die(aff->v->ctx, isl_error_invalid,
 272                         "position out of bounds", return -1);
 273
 274         pos += isl_local_space_offset(aff->ls, type);
 275         isl_int_set(*v, aff->v->el[1 + pos]);
 276
 277         return 0;
 278 }
 279
 280 __isl_give isl_aff *isl_aff_set_denominator(__isl_take isl_aff *aff, isl_int v)
 281 {
 282         aff = isl_aff_cow(aff);
 283         if (!aff)
 284                 return NULL;
 285
 286         aff->v = isl_vec_cow(aff->v);
 287         if (!aff->v)
 288                 return isl_aff_free(aff);
 289
 290         isl_int_set(aff->v->el[0], v);
 291
 292         return aff;
 293 }
 294
 295 __isl_give isl_aff *isl_aff_set_constant(__isl_take isl_aff *aff, isl_int v)
 296 {
 297         aff = isl_aff_cow(aff);
 298         if (!aff)
 299                 return NULL;
 300
 301         aff->v = isl_vec_cow(aff->v);
 302         if (!aff->v)
 303                 return isl_aff_free(aff);
 304
 305         isl_int_set(aff->v->el[1], v);
 306
 307         return aff;
 308 }
 309
 310 __isl_give isl_aff *isl_aff_add_constant(__isl_take isl_aff *aff, isl_int v)
 311 {
 312         if (isl_int_is_zero(v))
 313                 return aff;
 314
 315         aff = isl_aff_cow(aff);
 316         if (!aff)
 317                 return NULL;
 318
 319         aff->v = isl_vec_cow(aff->v);
 320         if (!aff->v)
 321                 return isl_aff_free(aff);
 322
 323         isl_int_addmul(aff->v->el[1], aff->v->el[0], v);
 324
 325         return aff;
 326 }
 327
 328 __isl_give isl_aff *isl_aff_add_constant_si(__isl_take isl_aff *aff, int v)
 329 {
 330         isl_int t;
 331
 332         isl_int_init(t);
 333         isl_int_set_si(t, v);
 334         aff = isl_aff_add_constant(aff, t);
 335         isl_int_clear(t);
 336
 337         return aff;
 338 }
 339
 340 __isl_give isl_aff *isl_aff_set_constant_si(__isl_take isl_aff *aff, int v)
 341 {
 342         aff = isl_aff_cow(aff);
 343         if (!aff)
 344                 return NULL;
 345
 346         aff->v = isl_vec_cow(aff->v);
 347         if (!aff->v)
 348                 return isl_aff_free(aff);
 349
 350         isl_int_set_si(aff->v->el[1], v);
 351
 352         return aff;
 353 }
 354
 355 __isl_give isl_aff *isl_aff_set_coefficient(__isl_take isl_aff *aff,
 356         enum isl_dim_type type, int pos, isl_int v)
 357 {
 358         if (!aff)
 359                 return NULL;
 360
 361         if (pos >= isl_local_space_dim(aff->ls, type))
 362                 isl_die(aff->v->ctx, isl_error_invalid,
 363                         "position out of bounds", return isl_aff_free(aff));
 364
 365         aff = isl_aff_cow(aff);
 366         if (!aff)
 367                 return NULL;
 368
 369         aff->v = isl_vec_cow(aff->v);
 370         if (!aff->v)
 371                 return isl_aff_free(aff);
 372
 373         pos += isl_local_space_offset(aff->ls, type);
 374         isl_int_set(aff->v->el[1 + pos], v);
 375
 376         return aff;
 377 }
 378
 379 __isl_give isl_aff *isl_aff_set_coefficient_si(__isl_take isl_aff *aff,
 380         enum isl_dim_type type, int pos, int v)
 381 {
 382         if (!aff)
 383                 return NULL;
 384
 385         if (pos >= isl_local_space_dim(aff->ls, type))
 386                 isl_die(aff->v->ctx, isl_error_invalid,
 387                         "position out of bounds", return isl_aff_free(aff));
 388
 389         aff = isl_aff_cow(aff);
 390         if (!aff)
 391                 return NULL;
 392
 393         aff->v = isl_vec_cow(aff->v);
 394         if (!aff->v)
 395                 return isl_aff_free(aff);
 396
 397         pos += isl_local_space_offset(aff->ls, type);
 398         isl_int_set_si(aff->v->el[1 + pos], v);
 399
 400         return aff;
 401 }
 402
 403 __isl_give isl_aff *isl_aff_add_coefficient(__isl_take isl_aff *aff,
 404         enum isl_dim_type type, int pos, isl_int v)
 405 {
 406         if (!aff)
 407                 return NULL;
 408
 409         if (pos >= isl_local_space_dim(aff->ls, type))
 410                 isl_die(aff->v->ctx, isl_error_invalid,
 411                         "position out of bounds", return isl_aff_free(aff));
 412
 413         aff = isl_aff_cow(aff);
 414         if (!aff)
 415                 return NULL;
 416
 417         aff->v = isl_vec_cow(aff->v);
 418         if (!aff->v)
 419                 return isl_aff_free(aff);
 420
 421         pos += isl_local_space_offset(aff->ls, type);
 422         isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v);
 423
 424         return aff;
 425 }
 426
 427 __isl_give isl_aff *isl_aff_add_coefficient_si(__isl_take isl_aff *aff,
 428         enum isl_dim_type type, int pos, int v)
 429 {
 430         isl_int t;
 431
 432         isl_int_init(t);
 433         isl_int_set_si(t, v);
 434         aff = isl_aff_add_coefficient(aff, type, pos, t);
 435         isl_int_clear(t);
 436
 437         return aff;
 438 }
 439
 440 __isl_give isl_div *isl_aff_get_div(__isl_keep isl_aff *aff, int pos)
 441 {
 442         if (!aff)
 443                 return NULL;
 444
 445         return isl_local_space_get_div(aff->ls, pos);
 446 }
 447
 448 __isl_give isl_aff *isl_aff_neg(__isl_take isl_aff *aff)
 449 {
 450         aff = isl_aff_cow(aff);
 451         if (!aff)
 452                 return NULL;
 453         aff->v = isl_vec_cow(aff->v);
 454         if (!aff->v)
 455                 return isl_aff_free(aff);
 456
 457         isl_seq_neg(aff->v->el + 1, aff->v->el + 1, aff->v->size - 1);
 458
 459         return aff;
 460 }
 461
 462 /* Given f, return floor(f).
 463  * If f is an integer expression, then just return f.
 464  * Otherwise, if f = g/m, write g = q m + r,
 465  * create a new div d = [r/m] and return the expression q + d.
 466  * The coefficients in r are taken to lie between -m/2 and m/2.
 467  */
 468 __isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff)
 469 {
 470         int i;
 471         int size;
 472         isl_ctx *ctx;
 473         isl_vec *div;
 474
 475         if (!aff)
 476                 return NULL;
 477
 478         if (isl_int_is_one(aff->v->el[0]))
 479                 return aff;
 480
 481         aff = isl_aff_cow(aff);
 482         if (!aff)
 483                 return NULL;
 484
 485         aff->v = isl_vec_cow(aff->v);
 486         div = isl_vec_copy(aff->v);
 487         div = isl_vec_cow(div);
 488         if (!div)
 489                 return isl_aff_free(aff);
 490
 491         ctx = isl_aff_get_ctx(aff);
 492         isl_int_fdiv_q(aff->v->el[0], aff->v->el[0], ctx->two);
 493         for (i = 1; i < aff->v->size; ++i) {
 494                 isl_int_fdiv_r(div->el[i], div->el[i], div->el[0]);
 495                 isl_int_fdiv_q(aff->v->el[i], aff->v->el[i], div->el[0]);
 496                 if (isl_int_gt(div->el[i], aff->v->el[0])) {
 497                         isl_int_sub(div->el[i], div->el[i], div->el[0]);
 498                         isl_int_add_ui(aff->v->el[i], aff->v->el[i], 1);
 499                 }
 500         }
 501
 502         aff->ls = isl_local_space_add_div(aff->ls, div);
 503         if (!aff->ls)
 504                 return isl_aff_free(aff);
 505
 506         size = aff->v->size;
 507         aff->v = isl_vec_extend(aff->v, size + 1);
 508         if (!aff->v)
 509                 return isl_aff_free(aff);
 510         isl_int_set_si(aff->v->el[0], 1);
 511         isl_int_set_si(aff->v->el[size], 1);
 512
 513         return aff;
 514 }
 515
 516 /* Compute
 517  *
 518  *      aff mod m = aff - m * floor(aff/m)
 519  */
 520 __isl_give isl_aff *isl_aff_mod(__isl_take isl_aff *aff, isl_int m)
 521 {
 522         isl_aff *res;
 523
 524         res = isl_aff_copy(aff);
 525         aff = isl_aff_scale_down(aff, m);
 526         aff = isl_aff_floor(aff);
 527         aff = isl_aff_scale(aff, m);
 528         res = isl_aff_sub(res, aff);
 529
 530         return res;
 531 }
 532
 533 /* Compute
 534  *
 535  *      pwaff mod m = pwaff - m * floor(pwaff/m)
 536  */
 537 __isl_give isl_pw_aff *isl_pw_aff_mod(__isl_take isl_pw_aff *pwaff, isl_int m)
 538 {
 539         isl_pw_aff *res;
 540
 541         res = isl_pw_aff_copy(pwaff);
 542         pwaff = isl_pw_aff_scale_down(pwaff, m);
 543         pwaff = isl_pw_aff_floor(pwaff);
 544         pwaff = isl_pw_aff_scale(pwaff, m);
 545         res = isl_pw_aff_sub(res, pwaff);
 546
 547         return res;
 548 }
 549
 550 /* Given f, return ceil(f).
 551  * If f is an integer expression, then just return f.
 552  * Otherwise, create a new div d = [-f] and return the expression -d.
 553  */
 554 __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff)
 555 {
 556         if (!aff)
 557                 return NULL;
 558
 559         if (isl_int_is_one(aff->v->el[0]))
 560                 return aff;
 561
 562         aff = isl_aff_neg(aff);
 563         aff = isl_aff_floor(aff);
 564         aff = isl_aff_neg(aff);
 565
 566         return aff;
 567 }
 568
 569 /* Apply the expansion computed by isl_merge_divs.
 570  * The expansion itself is given by "exp" while the resulting
 571  * list of divs is given by "div".
 572  */
 573 __isl_give isl_aff *isl_aff_expand_divs( __isl_take isl_aff *aff,
 574         __isl_take isl_mat *div, int *exp)
 575 {
 576         int i, j;
 577         int old_n_div;
 578         int new_n_div;
 579         int offset;
 580
 581         aff = isl_aff_cow(aff);
 582         if (!aff || !div)
 583                 goto error;
 584
 585         old_n_div = isl_local_space_dim(aff->ls, isl_dim_div);
 586         new_n_div = isl_mat_rows(div);
 587         if (new_n_div < old_n_div)
 588                 isl_die(isl_mat_get_ctx(div), isl_error_invalid,
 589                         "not an expansion", goto error);
 590
 591         aff->v = isl_vec_extend(aff->v, aff->v->size + new_n_div - old_n_div);
 592         if (!aff->v)
 593                 goto error;
 594
 595         offset = 1 + isl_local_space_offset(aff->ls, isl_dim_div);
 596         j = old_n_div - 1;
 597         for (i = new_n_div - 1; i >= 0; --i) {
 598                 if (j >= 0 && exp[j] == i) {
 599                         if (i != j)
 600                                 isl_int_swap(aff->v->el[offset + i],
 601                                              aff->v->el[offset + j]);
 602                         j--;
 603                 } else
 604                         isl_int_set_si(aff->v->el[offset + i], 0);
 605         }
 606
 607         aff->ls = isl_local_space_replace_divs(aff->ls, isl_mat_copy(div));
 608         if (!aff->ls)
 609                 goto error;
 610         isl_mat_free(div);
 611         return aff;
 612 error:
 613         isl_aff_free(aff);
 614         isl_mat_free(div);
 615         return NULL;
 616 }
 617
 618 /* Add two affine expressions that live in the same local space.
 619  */
 620 static __isl_give isl_aff *add_expanded(__isl_take isl_aff *aff1,
 621         __isl_take isl_aff *aff2)
 622 {
 623         isl_int gcd, f;
 624
 625         aff1 = isl_aff_cow(aff1);
 626         if (!aff1 || !aff2)
 627                 goto error;
 628
 629         aff1->v = isl_vec_cow(aff1->v);
 630         if (!aff1->v)
 631                 goto error;
 632
 633         isl_int_init(gcd);
 634         isl_int_init(f);
 635         isl_int_gcd(gcd, aff1->v->el[0], aff2->v->el[0]);
 636         isl_int_divexact(f, aff2->v->el[0], gcd);
 637         isl_seq_scale(aff1->v->el + 1, aff1->v->el + 1, f, aff1->v->size - 1);
 638         isl_int_divexact(f, aff1->v->el[0], gcd);
 639         isl_seq_addmul(aff1->v->el + 1, f, aff2->v->el + 1, aff1->v->size - 1);
 640         isl_int_divexact(f, aff2->v->el[0], gcd);
 641         isl_int_mul(aff1->v->el[0], aff1->v->el[0], f);
 642         isl_int_clear(f);
 643         isl_int_clear(gcd);
 644
 645         isl_aff_free(aff2);
 646         return aff1;
 647 error:
 648         isl_aff_free(aff1);
 649         isl_aff_free(aff2);
 650         return NULL;
 651 }
 652
 653 __isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
 654         __isl_take isl_aff *aff2)
 655 {
 656         isl_ctx *ctx;
 657         int *exp1 = NULL;
 658         int *exp2 = NULL;
 659         isl_mat *div;
 660
 661         if (!aff1 || !aff2)
 662                 goto error;
 663
 664         ctx = isl_aff_get_ctx(aff1);
 665         if (!isl_dim_equal(aff1->ls->dim, aff2->ls->dim))
 666                 isl_die(ctx, isl_error_invalid,
 667                         "spaces don't match", goto error);
 668
 669         if (aff1->ls->div->n_row == 0 && aff2->ls->div->n_row == 0)
 670                 return add_expanded(aff1, aff2);
 671
 672         exp1 = isl_alloc_array(ctx, int, aff1->ls->div->n_row);
 673         exp2 = isl_alloc_array(ctx, int, aff2->ls->div->n_row);
 674         if (!exp1 || !exp2)
 675                 goto error;
 676
 677         div = isl_merge_divs(aff1->ls->div, aff2->ls->div, exp1, exp2);
 678         aff1 = isl_aff_expand_divs(aff1, isl_mat_copy(div), exp1);
 679         aff2 = isl_aff_expand_divs(aff2, div, exp2);
 680         free(exp1);
 681         free(exp2);
 682
 683         return add_expanded(aff1, aff2);
 684 error:
 685         free(exp1);
 686         free(exp2);
 687         isl_aff_free(aff1);
 688         isl_aff_free(aff2);
 689         return NULL;
 690 }
 691
 692 __isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
 693         __isl_take isl_aff *aff2)
 694 {
 695         return isl_aff_add(aff1, isl_aff_neg(aff2));
 696 }
 697
 698 __isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f)
 699 {
 700         isl_int gcd;
 701
 702         if (isl_int_is_one(f))
 703                 return aff;
 704
 705         aff = isl_aff_cow(aff);
 706         if (!aff)
 707                 return NULL;
 708         aff->v = isl_vec_cow(aff->v);
 709         if (!aff->v)
 710                 return isl_aff_free(aff);
 711
 712         isl_int_init(gcd);
 713         isl_int_gcd(gcd, aff->v->el[0], f);
 714         isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd);
 715         isl_int_divexact(gcd, f, gcd);
 716         isl_seq_scale(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
 717         isl_int_clear(gcd);
 718
 719         return aff;
 720 }
 721
 722 __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f)
 723 {
 724         isl_int gcd;
 725
 726         if (isl_int_is_one(f))
 727                 return aff;
 728
 729         aff = isl_aff_cow(aff);
 730         if (!aff)
 731                 return NULL;
 732         aff->v = isl_vec_cow(aff->v);
 733         if (!aff->v)
 734                 return isl_aff_free(aff);
 735
 736         isl_int_init(gcd);
 737         isl_seq_gcd(aff->v->el + 1, aff->v->size - 1, &gcd);
 738         isl_int_gcd(gcd, gcd, f);
 739         isl_seq_scale_down(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
 740         isl_int_divexact(gcd, f, gcd);
 741         isl_int_mul(aff->v->el[0], aff->v->el[0], gcd);
 742         isl_int_clear(gcd);
 743
 744         return aff;
 745 }
 746
 747 __isl_give isl_aff *isl_aff_scale_down_ui(__isl_take isl_aff *aff, unsigned f)
 748 {
 749         isl_int v;
 750
 751         if (f == 1)
 752                 return aff;
 753
 754         isl_int_init(v);
 755         isl_int_set_ui(v, f);
 756         aff = isl_aff_scale_down(aff, v);
 757         isl_int_clear(v);
 758
 759         return aff;
 760 }
 761
 762 __isl_give isl_aff *isl_aff_set_dim_name(__isl_take isl_aff *aff,
 763         enum isl_dim_type type, unsigned pos, const char *s)
 764 {
 765         aff = isl_aff_cow(aff);
 766         if (!aff)
 767                 return NULL;
 768         aff->ls = isl_local_space_set_dim_name(aff->ls, type, pos, s);
 769         if (!aff->ls)
 770                 return isl_aff_free(aff);
 771
 772         return aff;
 773 }
 774
 775 /* Exploit the equalities in "eq" to simplify the affine expression
 776  * and the expressions of the integer divisions in the local space.
 777  * The integer divisions in this local space are assumed to appear
 778  * as regular dimensions in "eq".
 779  */
 780 static __isl_give isl_aff *isl_aff_substitute_equalities_lifted(
 781         __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
 782 {
 783         int i, j;
 784         unsigned total;
 785         unsigned n_div;
 786
 787         if (!eq)
 788                 goto error;
 789         if (eq->n_eq == 0) {
 790                 isl_basic_set_free(eq);
 791                 return aff;
 792         }
 793
 794         aff = isl_aff_cow(aff);
 795         if (!aff)
 796                 goto error;
 797
 798         aff->ls = isl_local_space_substitute_equalities(aff->ls,
 799                                                         isl_basic_set_copy(eq));
 800         if (!aff->ls)
 801                 goto error;
 802
 803         total = 1 + isl_dim_total(eq->dim);
 804         n_div = eq->n_div;
 805         for (i = 0; i < eq->n_eq; ++i) {
 806                 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
 807                 if (j < 0 || j == 0 || j >= total)
 808                         continue;
 809
 810                 isl_seq_elim(aff->v->el + 1, eq->eq[i], j, total,
 811                                 &aff->v->el[0]);
 812         }
 813
 814         isl_basic_set_free(eq);
 815         return aff;
 816 error:
 817         isl_basic_set_free(eq);
 818         isl_aff_free(aff);
 819         return NULL;
 820 }
 821
 822 /* Exploit the equalities in "eq" to simplify the affine expression
 823  * and the expressions of the integer divisions in the local space.
 824  */
 825 static __isl_give isl_aff *isl_aff_substitute_equalities(
 826         __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
 827 {
 828         int n_div;
 829
 830         if (!aff || !eq)
 831                 goto error;
 832         n_div = isl_local_space_dim(aff->ls, isl_dim_div);
 833         if (n_div > 0)
 834                 eq = isl_basic_set_add(eq, isl_dim_set, n_div);
 835         return isl_aff_substitute_equalities_lifted(aff, eq);
 836 error:
 837         isl_basic_set_free(eq);
 838         isl_aff_free(aff);
 839         return NULL;
 840 }
 841
 842 /* Look for equalities among the variables shared by context and aff
 843  * and the integer divisions of aff, if any.
 844  * The equalities are then used to eliminate coefficients and/or integer
 845  * divisions from aff.
 846  */
 847 __isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff,
 848         __isl_take isl_set *context)
 849 {
 850         isl_basic_set *hull;
 851         int n_div;
 852
 853         if (!aff)
 854                 goto error;
 855         n_div = isl_local_space_dim(aff->ls, isl_dim_div);
 856         if (n_div > 0) {
 857                 isl_basic_set *bset;
 858                 context = isl_set_add_dims(context, isl_dim_set, n_div);
 859                 bset = isl_basic_set_from_local_space(
 860                                             isl_aff_get_local_space(aff));
 861                 bset = isl_basic_set_lift(bset);
 862                 bset = isl_basic_set_flatten(bset);
 863                 context = isl_set_intersect(context,
 864                                             isl_set_from_basic_set(bset));
 865         }
 866
 867         hull = isl_set_affine_hull(context);
 868         return isl_aff_substitute_equalities_lifted(aff, hull);
 869 error:
 870         isl_aff_free(aff);
 871         isl_set_free(context);
 872         return NULL;
 873 }
 874
 875 /* Return a basic set containing those elements in the space
 876  * of aff where it is non-negative.
 877  */
 878 __isl_give isl_basic_set *isl_aff_nonneg_basic_set(__isl_take isl_aff *aff)
 879 {
 880         isl_constraint *ineq;
 881
 882         ineq = isl_inequality_from_aff(aff);
 883
 884         return isl_basic_set_from_constraint(ineq);
 885 }
 886
 887 /* Return a basic set containing those elements in the space
 888  * of aff where it is zero.
 889  */
 890 __isl_give isl_basic_set *isl_aff_zero_basic_set(__isl_take isl_aff *aff)
 891 {
 892         isl_constraint *ineq;
 893
 894         ineq = isl_equality_from_aff(aff);
 895
 896         return isl_basic_set_from_constraint(ineq);
 897 }
 898
 899 /* Return a basic set containing those elements in the shared space
 900  * of aff1 and aff2 where aff1 is greater than or equal to aff2.
 901  */
 902 __isl_give isl_basic_set *isl_aff_ge_basic_set(__isl_take isl_aff *aff1,
 903         __isl_take isl_aff *aff2)
 904 {
 905         aff1 = isl_aff_sub(aff1, aff2);
 906
 907         return isl_aff_nonneg_basic_set(aff1);
 908 }
 909
 910 __isl_give isl_aff *isl_aff_add_on_domain(__isl_keep isl_set *dom,
 911         __isl_take isl_aff *aff1, __isl_take isl_aff *aff2)
 912 {
 913         aff1 = isl_aff_add(aff1, aff2);
 914         aff1 = isl_aff_gist(aff1, isl_set_copy(dom));
 915         return aff1;
 916 }
 917
 918 int isl_aff_is_empty(__isl_keep isl_aff *aff)
 919 {
 920         if (!aff)
 921                 return -1;
 922
 923         return 0;
 924 }
 925
 926 /* Set active[i] to 1 if the dimension at position i is involved
 927  * in the affine expression.
 928  */
 929 static int set_active(__isl_keep isl_aff *aff, int *active)
 930 {
 931         int i, j;
 932         unsigned total;
 933         unsigned offset;
 934
 935         if (!aff || !active)
 936                 return -1;
 937
 938         total = aff->v->size - 2;
 939         for (i = 0; i < total; ++i)
 940                 active[i] = !isl_int_is_zero(aff->v->el[2 + i]);
 941
 942         offset = isl_local_space_offset(aff->ls, isl_dim_div) - 1;
 943         for (i = aff->ls->div->n_row - 1; i >= 0; --i) {
 944                 if (!active[offset + i])
 945                         continue;
 946                 for (j = 0; j < total; ++j)
 947                         active[j] |=
 948                                 !isl_int_is_zero(aff->ls->div->row[i][2 + j]);
 949         }
 950
 951         return 0;
 952 }
 953
 954 /* Check whether the given affine expression has non-zero coefficient
 955  * for any dimension in the given range or if any of these dimensions
 956  * appear with non-zero coefficients in any of the integer divisions
 957  * involved in the affine expression.
 958  */
 959 int isl_aff_involves_dims(__isl_keep isl_aff *aff,
 960         enum isl_dim_type type, unsigned first, unsigned n)
 961 {
 962         int i;
 963         isl_ctx *ctx;
 964         int *active = NULL;
 965         int involves = 0;
 966
 967         if (!aff)
 968                 return -1;
 969         if (n == 0)
 970                 return 0;
 971
 972         ctx = isl_aff_get_ctx(aff);
 973         if (first + n > isl_aff_dim(aff, type))
 974                 isl_die(ctx, isl_error_invalid,
 975                         "range out of bounds", return -1);
 976
 977         active = isl_calloc_array(ctx, int,
 978                                   isl_local_space_dim(aff->ls, isl_dim_all));
 979         if (set_active(aff, active) < 0)
 980                 goto error;
 981
 982         first += isl_local_space_offset(aff->ls, type) - 1;
 983         for (i = 0; i < n; ++i)
 984                 if (active[first + i]) {
 985                         involves = 1;
 986                         break;
 987                 }
 988
 989         free(active);
 990
 991         return involves;
 992 error:
 993         free(active);
 994         return -1;
 995 }
 996
 997 __isl_give isl_aff *isl_aff_drop_dims(__isl_take isl_aff *aff,
 998         enum isl_dim_type type, unsigned first, unsigned n)
 999 {
1000         isl_ctx *ctx;
1001
1002         if (!aff)
1003                 return NULL;
1004         if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
1005                 return aff;
1006
1007         ctx = isl_aff_get_ctx(aff);
1008         if (first + n > isl_aff_dim(aff, type))
1009                 isl_die(ctx, isl_error_invalid, "range out of bounds",
1010                         return isl_aff_free(aff));
1011
1012         aff = isl_aff_cow(aff);
1013         if (!aff)
1014                 return NULL;
1015
1016         aff->ls = isl_local_space_drop_dims(aff->ls, type, first, n);
1017         if (!aff->ls)
1018                 return isl_aff_free(aff);
1019
1020         first += 1 + isl_local_space_offset(aff->ls, type);
1021         aff->v = isl_vec_drop_els(aff->v, first, n);
1022         if (!aff->v)
1023                 return isl_aff_free(aff);
1024
1025         return aff;
1026 }
1027
1028 __isl_give isl_aff *isl_aff_insert_dims(__isl_take isl_aff *aff,
1029         enum isl_dim_type type, unsigned first, unsigned n)
1030 {
1031         isl_ctx *ctx;
1032
1033         if (!aff)
1034                 return NULL;
1035         if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
1036                 return aff;
1037
1038         ctx = isl_aff_get_ctx(aff);
1039         if (first > isl_aff_dim(aff, type))
1040                 isl_die(ctx, isl_error_invalid, "position out of bounds",
1041                         return isl_aff_free(aff));
1042
1043         aff = isl_aff_cow(aff);
1044         if (!aff)
1045                 return NULL;
1046
1047         aff->ls = isl_local_space_insert_dims(aff->ls, type, first, n);
1048         if (!aff->ls)
1049                 return isl_aff_free(aff);
1050
1051         first += 1 + isl_local_space_offset(aff->ls, type);
1052         aff->v = isl_vec_insert_zero_els(aff->v, first, n);
1053         if (!aff->v)
1054                 return isl_aff_free(aff);
1055
1056         return aff;
1057 }
1058
1059 __isl_give isl_aff *isl_aff_add_dims(__isl_take isl_aff *aff,
1060         enum isl_dim_type type, unsigned n)
1061 {
1062         unsigned pos;
1063
1064         pos = isl_aff_dim(aff, type);
1065
1066         return isl_aff_insert_dims(aff, type, pos, n);
1067 }
1068
1069 __isl_give isl_pw_aff *isl_pw_aff_add_dims(__isl_take isl_pw_aff *pwaff,
1070         enum isl_dim_type type, unsigned n)
1071 {
1072         unsigned pos;
1073
1074         pos = isl_pw_aff_dim(pwaff, type);
1075
1076         return isl_pw_aff_insert_dims(pwaff, type, pos, n);
1077 }
1078
1079 __isl_give isl_pw_aff *isl_pw_aff_set_tuple_id(__isl_take isl_pw_aff *pwaff,
1080         __isl_take isl_id *id)
1081 {
1082         isl_dim *dim;
1083
1084         dim = isl_pw_aff_get_dim(pwaff);
1085         dim = isl_dim_set_tuple_id(dim, isl_dim_set, id);
1086
1087         return isl_pw_aff_reset_dim(pwaff, dim);
1088 }
1089
1090 __isl_give isl_pw_aff *isl_pw_aff_from_aff(__isl_take isl_aff *aff)
1091 {
1092         isl_set *dom = isl_set_universe(isl_aff_get_dim(aff));
1093         return isl_pw_aff_alloc(dom, aff);
1094 }
1095
1096 #undef PW
1097 #define PW isl_pw_aff
1098 #undef EL
1099 #define EL isl_aff
1100 #undef EL_IS_ZERO
1101 #define EL_IS_ZERO is_empty
1102 #undef ZERO
1103 #define ZERO empty
1104 #undef IS_ZERO
1105 #define IS_ZERO is_empty
1106 #undef FIELD
1107 #define FIELD aff
1108
1109 #define NO_EVAL
1110 #define NO_OPT
1111 #define NO_MOVE_DIMS
1112 #define NO_LIFT
1113 #define NO_MORPH
1114
1115 #include <isl_pw_templ.c>
1116
1117 static __isl_give isl_set *align_params_pw_pw_set_and(
1118         __isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2,
1119         __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1120                                     __isl_take isl_pw_aff *pwaff2))
1121 {
1122         if (!pwaff1 || !pwaff2)
1123                 goto error;
1124         if (isl_dim_match(pwaff1->dim, isl_dim_param,
1125                           pwaff2->dim, isl_dim_param))
1126                 return fn(pwaff1, pwaff2);
1127         if (!isl_dim_has_named_params(pwaff1->dim) ||
1128             !isl_dim_has_named_params(pwaff2->dim))
1129                 isl_die(isl_pw_aff_get_ctx(pwaff1), isl_error_invalid,
1130                         "unaligned unnamed parameters", goto error);
1131         pwaff1 = isl_pw_aff_align_params(pwaff1, isl_pw_aff_get_dim(pwaff2));
1132         pwaff2 = isl_pw_aff_align_params(pwaff2, isl_pw_aff_get_dim(pwaff1));
1133         return fn(pwaff1, pwaff2);
1134 error:
1135         isl_pw_aff_free(pwaff1);
1136         isl_pw_aff_free(pwaff2);
1137         return NULL;
1138 }
1139
1140 /* Compute a piecewise quasi-affine expression with a domain that
1141  * is the union of those of pwaff1 and pwaff2 and such that on each
1142  * cell, the quasi-affine expression is the maximum of those of pwaff1
1143  * and pwaff2.  If only one of pwaff1 or pwaff2 is defined on a given
1144  * cell, then the associated expression is the defined one.
1145  */
1146 static __isl_give isl_pw_aff *pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1147         __isl_take isl_pw_aff *pwaff2)
1148 {
1149         int i, j, n;
1150         isl_pw_aff *res;
1151         isl_ctx *ctx;
1152         isl_set *set;
1153
1154         if (!pwaff1 || !pwaff2)
1155                 goto error;
1156
1157         ctx = isl_dim_get_ctx(pwaff1->dim);
1158         if (!isl_dim_equal(pwaff1->dim, pwaff2->dim))
1159                 isl_die(ctx, isl_error_invalid,
1160                         "arguments should live in same space", goto error);
1161
1162         if (isl_pw_aff_is_empty(pwaff1)) {
1163                 isl_pw_aff_free(pwaff1);
1164                 return pwaff2;
1165         }
1166
1167         if (isl_pw_aff_is_empty(pwaff2)) {
1168                 isl_pw_aff_free(pwaff2);
1169                 return pwaff1;
1170         }
1171
1172         n = 2 * (pwaff1->n + 1) * (pwaff2->n + 1);
1173         res = isl_pw_aff_alloc_(isl_dim_copy(pwaff1->dim), n);
1174
1175         for (i = 0; i < pwaff1->n; ++i) {
1176                 set = isl_set_copy(pwaff1->p[i].set);
1177                 for (j = 0; j < pwaff2->n; ++j) {
1178                         struct isl_set *common;
1179                         isl_set *ge;
1180
1181                         common = isl_set_intersect(
1182                                         isl_set_copy(pwaff1->p[i].set),
1183                                         isl_set_copy(pwaff2->p[j].set));
1184                         ge = isl_set_from_basic_set(isl_aff_ge_basic_set(
1185                                         isl_aff_copy(pwaff2->p[j].aff),
1186                                         isl_aff_copy(pwaff1->p[i].aff)));
1187                         ge = isl_set_intersect(common, ge);
1188                         if (isl_set_plain_is_empty(ge)) {
1189                                 isl_set_free(ge);
1190                                 continue;
1191                         }
1192                         set = isl_set_subtract(set, isl_set_copy(ge));
1193
1194                         res = isl_pw_aff_add_piece(res, ge,
1195                                                 isl_aff_copy(pwaff2->p[j].aff));
1196                 }
1197                 res = isl_pw_aff_add_piece(res, set,
1198                                                 isl_aff_copy(pwaff1->p[i].aff));
1199         }
1200
1201         for (j = 0; j < pwaff2->n; ++j) {
1202                 set = isl_set_copy(pwaff2->p[j].set);
1203                 for (i = 0; i < pwaff1->n; ++i)
1204                         set = isl_set_subtract(set,
1205                                         isl_set_copy(pwaff1->p[i].set));
1206                 res = isl_pw_aff_add_piece(res, set,
1207                                                 isl_aff_copy(pwaff2->p[j].aff));
1208         }
1209
1210         isl_pw_aff_free(pwaff1);
1211         isl_pw_aff_free(pwaff2);
1212
1213         return res;
1214 error:
1215         isl_pw_aff_free(pwaff1);
1216         isl_pw_aff_free(pwaff2);
1217         return NULL;
1218 }
1219
1220 __isl_give isl_pw_aff *isl_pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1221         __isl_take isl_pw_aff *pwaff2)
1222 {
1223         return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_union_max);
1224 }
1225
1226 /* Construct a map with as domain the domain of pwaff and
1227  * one-dimensional range corresponding to the affine expressions.
1228  */
1229 __isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1230 {
1231         int i;
1232         isl_dim *dim;
1233         isl_map *map;
1234
1235         if (!pwaff)
1236                 return NULL;
1237
1238         dim = isl_pw_aff_get_dim(pwaff);
1239         dim = isl_dim_from_domain(dim);
1240         dim = isl_dim_add(dim, isl_dim_out, 1);
1241         map = isl_map_empty(dim);
1242
1243         for (i = 0; i < pwaff->n; ++i) {
1244                 isl_basic_map *bmap;
1245                 isl_map *map_i;
1246
1247                 bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
1248                 map_i = isl_map_from_basic_map(bmap);
1249                 map_i = isl_map_intersect_domain(map_i,
1250                                                 isl_set_copy(pwaff->p[i].set));
1251                 map = isl_map_union_disjoint(map, map_i);
1252         }
1253
1254         isl_pw_aff_free(pwaff);
1255
1256         return map;
1257 }
1258
1259 /* Return a set containing those elements in the domain
1260  * of pwaff where it is non-negative.
1261  */
1262 __isl_give isl_set *isl_pw_aff_nonneg_set(__isl_take isl_pw_aff *pwaff)
1263 {
1264         int i;
1265         isl_set *set;
1266
1267         if (!pwaff)
1268                 return NULL;
1269
1270         set = isl_set_empty(isl_pw_aff_get_dim(pwaff));
1271
1272         for (i = 0; i < pwaff->n; ++i) {
1273                 isl_basic_set *bset;
1274                 isl_set *set_i;
1275
1276                 bset = isl_aff_nonneg_basic_set(isl_aff_copy(pwaff->p[i].aff));
1277                 set_i = isl_set_from_basic_set(bset);
1278                 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1279                 set = isl_set_union_disjoint(set, set_i);
1280         }
1281
1282         isl_pw_aff_free(pwaff);
1283
1284         return set;
1285 }
1286
1287 /* Return a set containing those elements in the domain
1288  * of pwaff where it is zero.
1289  */
1290 __isl_give isl_set *isl_pw_aff_zero_set(__isl_take isl_pw_aff *pwaff)
1291 {
1292         int i;
1293         isl_set *set;
1294
1295         if (!pwaff)
1296                 return NULL;
1297
1298         set = isl_set_empty(isl_pw_aff_get_dim(pwaff));
1299
1300         for (i = 0; i < pwaff->n; ++i) {
1301                 isl_basic_set *bset;
1302                 isl_set *set_i;
1303
1304                 bset = isl_aff_zero_basic_set(isl_aff_copy(pwaff->p[i].aff));
1305                 set_i = isl_set_from_basic_set(bset);
1306                 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1307                 set = isl_set_union_disjoint(set, set_i);
1308         }
1309
1310         isl_pw_aff_free(pwaff);
1311
1312         return set;
1313 }
1314
1315 /* Return a set containing those elements in the domain
1316  * of pwaff where it is not zero.
1317  */
1318 __isl_give isl_set *isl_pw_aff_non_zero_set(__isl_take isl_pw_aff *pwaff)
1319 {
1320         return isl_set_complement(isl_pw_aff_zero_set(pwaff));
1321 }
1322
1323 /* Return a set containing those elements in the shared domain
1324  * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
1325  *
1326  * We compute the difference on the shared domain and then construct
1327  * the set of values where this difference is non-negative.
1328  * If strict is set, we first subtract 1 from the difference.
1329  * If equal is set, we only return the elements where pwaff1 and pwaff2
1330  * are equal.
1331  */
1332 static __isl_give isl_set *pw_aff_gte_set(__isl_take isl_pw_aff *pwaff1,
1333         __isl_take isl_pw_aff *pwaff2, int strict, int equal)
1334 {
1335         isl_set *set1, *set2;
1336
1337         set1 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff1));
1338         set2 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff2));
1339         set1 = isl_set_intersect(set1, set2);
1340         pwaff1 = isl_pw_aff_intersect_domain(pwaff1, isl_set_copy(set1));
1341         pwaff2 = isl_pw_aff_intersect_domain(pwaff2, isl_set_copy(set1));
1342         pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_neg(pwaff2));
1343
1344         if (strict) {
1345                 isl_dim *dim = isl_set_get_dim(set1);
1346                 isl_aff *aff;
1347                 aff = isl_aff_zero(isl_local_space_from_dim(dim));
1348                 aff = isl_aff_add_constant_si(aff, -1);
1349                 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_alloc(set1, aff));
1350         } else
1351                 isl_set_free(set1);
1352
1353         if (equal)
1354                 return isl_pw_aff_zero_set(pwaff1);
1355         return isl_pw_aff_nonneg_set(pwaff1);
1356 }
1357
1358 /* Return a set containing those elements in the shared domain
1359  * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
1360  */
1361 static __isl_give isl_set *pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1362         __isl_take isl_pw_aff *pwaff2)
1363 {
1364         return pw_aff_gte_set(pwaff1, pwaff2, 0, 1);
1365 }
1366
1367 __isl_give isl_set *isl_pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1368         __isl_take isl_pw_aff *pwaff2)
1369 {
1370         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_eq_set);
1371 }
1372
1373 /* Return a set containing those elements in the shared domain
1374  * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
1375  */
1376 static __isl_give isl_set *pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1377         __isl_take isl_pw_aff *pwaff2)
1378 {
1379         return pw_aff_gte_set(pwaff1, pwaff2, 0, 0);
1380 }
1381
1382 __isl_give isl_set *isl_pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1383         __isl_take isl_pw_aff *pwaff2)
1384 {
1385         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ge_set);
1386 }
1387
1388 /* Return a set containing those elements in the shared domain
1389  * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
1390  */
1391 static __isl_give isl_set *pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1392         __isl_take isl_pw_aff *pwaff2)
1393 {
1394         return pw_aff_gte_set(pwaff1, pwaff2, 1, 0);
1395 }
1396
1397 __isl_give isl_set *isl_pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1398         __isl_take isl_pw_aff *pwaff2)
1399 {
1400         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_gt_set);
1401 }
1402
1403 __isl_give isl_set *isl_pw_aff_le_set(__isl_take isl_pw_aff *pwaff1,
1404         __isl_take isl_pw_aff *pwaff2)
1405 {
1406         return isl_pw_aff_ge_set(pwaff2, pwaff1);
1407 }
1408
1409 __isl_give isl_set *isl_pw_aff_lt_set(__isl_take isl_pw_aff *pwaff1,
1410         __isl_take isl_pw_aff *pwaff2)
1411 {
1412         return isl_pw_aff_gt_set(pwaff2, pwaff1);
1413 }
1414
1415 /* Return a set containing those elements in the shared domain
1416  * of the elements of list1 and list2 where each element in list1
1417  * has the relation specified by "fn" with each element in list2.
1418  */
1419 static __isl_give isl_set *pw_aff_list_set(__isl_take isl_pw_aff_list *list1,
1420         __isl_take isl_pw_aff_list *list2,
1421         __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1422                                     __isl_take isl_pw_aff *pwaff2))
1423 {
1424         int i, j;
1425         isl_ctx *ctx;
1426         isl_set *set;
1427
1428         if (!list1 || !list2)
1429                 goto error;
1430
1431         ctx = isl_pw_aff_list_get_ctx(list1);
1432         if (list1->n < 1 || list2->n < 1)
1433                 isl_die(ctx, isl_error_invalid,
1434                         "list should contain at least one element", goto error);
1435
1436         set = isl_set_universe(isl_pw_aff_get_dim(list1->p[0]));
1437         for (i = 0; i < list1->n; ++i)
1438                 for (j = 0; j < list2->n; ++j) {
1439                         isl_set *set_ij;
1440
1441                         set_ij = fn(isl_pw_aff_copy(list1->p[i]),
1442                                     isl_pw_aff_copy(list2->p[j]));
1443                         set = isl_set_intersect(set, set_ij);
1444                 }
1445
1446         isl_pw_aff_list_free(list1);
1447         isl_pw_aff_list_free(list2);
1448         return set;
1449 error:
1450         isl_pw_aff_list_free(list1);
1451         isl_pw_aff_list_free(list2);
1452         return NULL;
1453 }
1454
1455 /* Return a set containing those elements in the shared domain
1456  * of the elements of list1 and list2 where each element in list1
1457  * is equal to each element in list2.
1458  */
1459 __isl_give isl_set *isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list *list1,
1460         __isl_take isl_pw_aff_list *list2)
1461 {
1462         return pw_aff_list_set(list1, list2, &isl_pw_aff_eq_set);
1463 }
1464
1465 __isl_give isl_set *isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list *list1,
1466         __isl_take isl_pw_aff_list *list2)
1467 {
1468         return pw_aff_list_set(list1, list2, &isl_pw_aff_ne_set);
1469 }
1470
1471 /* Return a set containing those elements in the shared domain
1472  * of the elements of list1 and list2 where each element in list1
1473  * is less than or equal to each element in list2.
1474  */
1475 __isl_give isl_set *isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list *list1,
1476         __isl_take isl_pw_aff_list *list2)
1477 {
1478         return pw_aff_list_set(list1, list2, &isl_pw_aff_le_set);
1479 }
1480
1481 __isl_give isl_set *isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list *list1,
1482         __isl_take isl_pw_aff_list *list2)
1483 {
1484         return pw_aff_list_set(list1, list2, &isl_pw_aff_lt_set);
1485 }
1486
1487 __isl_give isl_set *isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list *list1,
1488         __isl_take isl_pw_aff_list *list2)
1489 {
1490         return pw_aff_list_set(list1, list2, &isl_pw_aff_ge_set);
1491 }
1492
1493 __isl_give isl_set *isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list *list1,
1494         __isl_take isl_pw_aff_list *list2)
1495 {
1496         return pw_aff_list_set(list1, list2, &isl_pw_aff_gt_set);
1497 }
1498
1499
1500 /* Return a set containing those elements in the shared domain
1501  * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
1502  */
1503 static __isl_give isl_set *pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1504         __isl_take isl_pw_aff *pwaff2)
1505 {
1506         isl_set *set_lt, *set_gt;
1507
1508         set_lt = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1),
1509                                    isl_pw_aff_copy(pwaff2));
1510         set_gt = isl_pw_aff_gt_set(pwaff1, pwaff2);
1511         return isl_set_union_disjoint(set_lt, set_gt);
1512 }
1513
1514 __isl_give isl_set *isl_pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1515         __isl_take isl_pw_aff *pwaff2)
1516 {
1517         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ne_set);
1518 }
1519
1520 __isl_give isl_pw_aff *isl_pw_aff_scale_down(__isl_take isl_pw_aff *pwaff,
1521         isl_int v)
1522 {
1523         int i;
1524
1525         if (isl_int_is_one(v))
1526                 return pwaff;
1527         if (!isl_int_is_pos(v))
1528                 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1529                         "factor needs to be positive",
1530                         return isl_pw_aff_free(pwaff));
1531         pwaff = isl_pw_aff_cow(pwaff);
1532         if (!pwaff)
1533                 return NULL;
1534         if (pwaff->n == 0)
1535                 return pwaff;
1536
1537         for (i = 0; i < pwaff->n; ++i) {
1538                 pwaff->p[i].aff = isl_aff_scale_down(pwaff->p[i].aff, v);
1539                 if (!pwaff->p[i].aff)
1540                         return isl_pw_aff_free(pwaff);
1541         }
1542
1543         return pwaff;
1544 }
1545
1546 __isl_give isl_pw_aff *isl_pw_aff_floor(__isl_take isl_pw_aff *pwaff)
1547 {
1548         int i;
1549
1550         pwaff = isl_pw_aff_cow(pwaff);
1551         if (!pwaff)
1552                 return NULL;
1553         if (pwaff->n == 0)
1554                 return pwaff;
1555
1556         for (i = 0; i < pwaff->n; ++i) {
1557                 pwaff->p[i].aff = isl_aff_floor(pwaff->p[i].aff);
1558                 if (!pwaff->p[i].aff)
1559                         return isl_pw_aff_free(pwaff);
1560         }
1561
1562         return pwaff;
1563 }
1564
1565 __isl_give isl_pw_aff *isl_pw_aff_ceil(__isl_take isl_pw_aff *pwaff)
1566 {
1567         int i;
1568
1569         pwaff = isl_pw_aff_cow(pwaff);
1570         if (!pwaff)
1571                 return NULL;
1572         if (pwaff->n == 0)
1573                 return pwaff;
1574
1575         for (i = 0; i < pwaff->n; ++i) {
1576                 pwaff->p[i].aff = isl_aff_ceil(pwaff->p[i].aff);
1577                 if (!pwaff->p[i].aff)
1578                         return isl_pw_aff_free(pwaff);
1579         }
1580
1581         return pwaff;
1582 }
1583
1584 /* Return an affine expression that is equal to pwaff_true for elements
1585  * in "cond" and to pwaff_false for elements not in "cond".
1586  * That is, return cond ? pwaff_true : pwaff_false;
1587  */
1588 __isl_give isl_pw_aff *isl_pw_aff_cond(__isl_take isl_set *cond,
1589         __isl_take isl_pw_aff *pwaff_true, __isl_take isl_pw_aff *pwaff_false)
1590 {
1591         isl_set *comp;
1592
1593         comp = isl_set_complement(isl_set_copy(cond));
1594         pwaff_true = isl_pw_aff_intersect_domain(pwaff_true, cond);
1595         pwaff_false = isl_pw_aff_intersect_domain(pwaff_false, comp);
1596
1597         return isl_pw_aff_add_disjoint(pwaff_true, pwaff_false);
1598 }
1599
1600 int isl_aff_is_cst(__isl_keep isl_aff *aff)
1601 {
1602         if (!aff)
1603                 return -1;
1604
1605         return isl_seq_first_non_zero(aff->v->el + 2, aff->v->size - 2) == -1;
1606 }
1607
1608 /* Check whether pwaff is a piecewise constant.
1609  */
1610 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff)
1611 {
1612         int i;
1613
1614         if (!pwaff)
1615                 return -1;
1616
1617         for (i = 0; i < pwaff->n; ++i) {
1618                 int is_cst = isl_aff_is_cst(pwaff->p[i].aff);
1619                 if (is_cst < 0 || !is_cst)
1620                         return is_cst;
1621         }
1622
1623         return 1;
1624 }
1625
1626 __isl_give isl_aff *isl_aff_mul(__isl_take isl_aff *aff1,
1627         __isl_take isl_aff *aff2)
1628 {
1629         if (!isl_aff_is_cst(aff2) && isl_aff_is_cst(aff1))
1630                 return isl_aff_mul(aff2, aff1);
1631
1632         if (!isl_aff_is_cst(aff2))
1633                 isl_die(isl_aff_get_ctx(aff1), isl_error_invalid,
1634                         "at least one affine expression should be constant",
1635                         goto error);
1636
1637         aff1 = isl_aff_cow(aff1);
1638         if (!aff1 || !aff2)
1639                 goto error;
1640
1641         aff1 = isl_aff_scale(aff1, aff2->v->el[1]);
1642         aff1 = isl_aff_scale_down(aff1, aff2->v->el[0]);
1643
1644         isl_aff_free(aff2);
1645         return aff1;
1646 error:
1647         isl_aff_free(aff1);
1648         isl_aff_free(aff2);
1649         return NULL;
1650 }
1651
1652 static __isl_give isl_pw_aff *pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
1653         __isl_take isl_pw_aff *pwaff2)
1654 {
1655         int i, j, n;
1656         isl_pw_aff *res;
1657
1658         if (!pwaff1 || !pwaff2)
1659                 goto error;
1660
1661         n = pwaff1->n * pwaff2->n;
1662         res = isl_pw_aff_alloc_(isl_dim_copy(pwaff1->dim), n);
1663
1664         for (i = 0; i < pwaff1->n; ++i) {
1665                 for (j = 0; j < pwaff2->n; ++j) {
1666                         isl_set *common;
1667                         isl_aff *prod;
1668                         common = isl_set_intersect(
1669                                         isl_set_copy(pwaff1->p[i].set),
1670                                         isl_set_copy(pwaff2->p[j].set));
1671                         if (isl_set_plain_is_empty(common)) {
1672                                 isl_set_free(common);
1673                                 continue;
1674                         }
1675
1676                         prod = isl_aff_mul(isl_aff_copy(pwaff1->p[i].aff),
1677                                             isl_aff_copy(pwaff2->p[j].aff));
1678
1679                         res = isl_pw_aff_add_piece(res, common, prod);
1680                 }
1681         }
1682
1683         isl_pw_aff_free(pwaff1);
1684         isl_pw_aff_free(pwaff2);
1685         return res;
1686 error:
1687         isl_pw_aff_free(pwaff1);
1688         isl_pw_aff_free(pwaff2);
1689         return NULL;
1690 }
1691
1692 __isl_give isl_pw_aff *isl_pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
1693         __isl_take isl_pw_aff *pwaff2)
1694 {
1695         return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_mul);
1696 }
1697
1698 static __isl_give isl_pw_aff *pw_aff_min(__isl_take isl_pw_aff *pwaff1,
1699         __isl_take isl_pw_aff *pwaff2)
1700 {
1701         isl_set *le;
1702
1703         le = isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1),
1704                                 isl_pw_aff_copy(pwaff2));
1705         return isl_pw_aff_cond(le, pwaff1, pwaff2);
1706 }
1707
1708 __isl_give isl_pw_aff *isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1,
1709         __isl_take isl_pw_aff *pwaff2)
1710 {
1711         return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_min);
1712 }
1713
1714 static __isl_give isl_pw_aff *pw_aff_max(__isl_take isl_pw_aff *pwaff1,
1715         __isl_take isl_pw_aff *pwaff2)
1716 {
1717         isl_set *le;
1718
1719         le = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1),
1720                                 isl_pw_aff_copy(pwaff2));
1721         return isl_pw_aff_cond(le, pwaff1, pwaff2);
1722 }
1723
1724 __isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1,
1725         __isl_take isl_pw_aff *pwaff2)
1726 {
1727         return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_max);
1728 }
1729
1730 static __isl_give isl_pw_aff *pw_aff_list_reduce(
1731         __isl_take isl_pw_aff_list *list,
1732         __isl_give isl_pw_aff *(*fn)(__isl_take isl_pw_aff *pwaff1,
1733                                         __isl_take isl_pw_aff *pwaff2))
1734 {
1735         int i;
1736         isl_ctx *ctx;
1737         isl_pw_aff *res;
1738
1739         if (!list)
1740                 return NULL;
1741
1742         ctx = isl_pw_aff_list_get_ctx(list);
1743         if (list->n < 1)
1744                 isl_die(ctx, isl_error_invalid,
1745                         "list should contain at least one element",
1746                         return isl_pw_aff_list_free(list));
1747
1748         res = isl_pw_aff_copy(list->p[0]);
1749         for (i = 1; i < list->n; ++i)
1750                 res = fn(res, isl_pw_aff_copy(list->p[i]));
1751
1752         isl_pw_aff_list_free(list);
1753         return res;
1754 }
1755
1756 /* Return an isl_pw_aff that maps each element in the intersection of the
1757  * domains of the elements of list to the minimal corresponding affine
1758  * expression.
1759  */
1760 __isl_give isl_pw_aff *isl_pw_aff_list_min(__isl_take isl_pw_aff_list *list)
1761 {
1762         return pw_aff_list_reduce(list, &isl_pw_aff_min);
1763 }
1764
1765 /* Return an isl_pw_aff that maps each element in the intersection of the
1766  * domains of the elements of list to the maximal corresponding affine
1767  * expression.
1768  */
1769 __isl_give isl_pw_aff *isl_pw_aff_list_max(__isl_take isl_pw_aff_list *list)
1770 {
1771         return pw_aff_list_reduce(list, &isl_pw_aff_max);
1772 }