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 __isl_give isl_aff *isl_aff_normalize(__isl_take isl_aff *aff)
 547 {
 548         if (!aff)
 549                 return NULL;
 550         aff->v = isl_vec_normalize(aff->v);
 551         if (!aff->v)
 552                 return isl_aff_free(aff);
 553         return aff;
 554 }
 555
 556 /* Given f, return floor(f).
 557  * If f is an integer expression, then just return f.
 558  * Otherwise, if f = g/m, write g = q m + r,
 559  * create a new div d = [r/m] and return the expression q + d.
 560  * The coefficients in r are taken to lie between -m/2 and m/2.
 561  */
 562 __isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff)
 563 {
 564         int i;
 565         int size;
 566         isl_ctx *ctx;
 567         isl_vec *div;
 568
 569         if (!aff)
 570                 return NULL;
 571
 572         if (isl_int_is_one(aff->v->el[0]))
 573                 return aff;
 574
 575         aff = isl_aff_cow(aff);
 576         if (!aff)
 577                 return NULL;
 578
 579         aff->v = isl_vec_cow(aff->v);
 580         div = isl_vec_copy(aff->v);
 581         div = isl_vec_cow(div);
 582         if (!div)
 583                 return isl_aff_free(aff);
 584
 585         ctx = isl_aff_get_ctx(aff);
 586         isl_int_fdiv_q(aff->v->el[0], aff->v->el[0], ctx->two);
 587         for (i = 1; i < aff->v->size; ++i) {
 588                 isl_int_fdiv_r(div->el[i], div->el[i], div->el[0]);
 589                 isl_int_fdiv_q(aff->v->el[i], aff->v->el[i], div->el[0]);
 590                 if (isl_int_gt(div->el[i], aff->v->el[0])) {
 591                         isl_int_sub(div->el[i], div->el[i], div->el[0]);
 592                         isl_int_add_ui(aff->v->el[i], aff->v->el[i], 1);
 593                 }
 594         }
 595
 596         aff->ls = isl_local_space_add_div(aff->ls, div);
 597         if (!aff->ls)
 598                 return isl_aff_free(aff);
 599
 600         size = aff->v->size;
 601         aff->v = isl_vec_extend(aff->v, size + 1);
 602         if (!aff->v)
 603                 return isl_aff_free(aff);
 604         isl_int_set_si(aff->v->el[0], 1);
 605         isl_int_set_si(aff->v->el[size], 1);
 606
 607         return aff;
 608 }
 609
 610 /* Compute
 611  *
 612  *      aff mod m = aff - m * floor(aff/m)
 613  */
 614 __isl_give isl_aff *isl_aff_mod(__isl_take isl_aff *aff, isl_int m)
 615 {
 616         isl_aff *res;
 617
 618         res = isl_aff_copy(aff);
 619         aff = isl_aff_scale_down(aff, m);
 620         aff = isl_aff_floor(aff);
 621         aff = isl_aff_scale(aff, m);
 622         res = isl_aff_sub(res, aff);
 623
 624         return res;
 625 }
 626
 627 /* Compute
 628  *
 629  *      pwaff mod m = pwaff - m * floor(pwaff/m)
 630  */
 631 __isl_give isl_pw_aff *isl_pw_aff_mod(__isl_take isl_pw_aff *pwaff, isl_int m)
 632 {
 633         isl_pw_aff *res;
 634
 635         res = isl_pw_aff_copy(pwaff);
 636         pwaff = isl_pw_aff_scale_down(pwaff, m);
 637         pwaff = isl_pw_aff_floor(pwaff);
 638         pwaff = isl_pw_aff_scale(pwaff, m);
 639         res = isl_pw_aff_sub(res, pwaff);
 640
 641         return res;
 642 }
 643
 644 /* Given f, return ceil(f).
 645  * If f is an integer expression, then just return f.
 646  * Otherwise, create a new div d = [-f] and return the expression -d.
 647  */
 648 __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff)
 649 {
 650         if (!aff)
 651                 return NULL;
 652
 653         if (isl_int_is_one(aff->v->el[0]))
 654                 return aff;
 655
 656         aff = isl_aff_neg(aff);
 657         aff = isl_aff_floor(aff);
 658         aff = isl_aff_neg(aff);
 659
 660         return aff;
 661 }
 662
 663 /* Apply the expansion computed by isl_merge_divs.
 664  * The expansion itself is given by "exp" while the resulting
 665  * list of divs is given by "div".
 666  */
 667 __isl_give isl_aff *isl_aff_expand_divs( __isl_take isl_aff *aff,
 668         __isl_take isl_mat *div, int *exp)
 669 {
 670         int i, j;
 671         int old_n_div;
 672         int new_n_div;
 673         int offset;
 674
 675         aff = isl_aff_cow(aff);
 676         if (!aff || !div)
 677                 goto error;
 678
 679         old_n_div = isl_local_space_dim(aff->ls, isl_dim_div);
 680         new_n_div = isl_mat_rows(div);
 681         if (new_n_div < old_n_div)
 682                 isl_die(isl_mat_get_ctx(div), isl_error_invalid,
 683                         "not an expansion", goto error);
 684
 685         aff->v = isl_vec_extend(aff->v, aff->v->size + new_n_div - old_n_div);
 686         if (!aff->v)
 687                 goto error;
 688
 689         offset = 1 + isl_local_space_offset(aff->ls, isl_dim_div);
 690         j = old_n_div - 1;
 691         for (i = new_n_div - 1; i >= 0; --i) {
 692                 if (j >= 0 && exp[j] == i) {
 693                         if (i != j)
 694                                 isl_int_swap(aff->v->el[offset + i],
 695                                              aff->v->el[offset + j]);
 696                         j--;
 697                 } else
 698                         isl_int_set_si(aff->v->el[offset + i], 0);
 699         }
 700
 701         aff->ls = isl_local_space_replace_divs(aff->ls, isl_mat_copy(div));
 702         if (!aff->ls)
 703                 goto error;
 704         isl_mat_free(div);
 705         return aff;
 706 error:
 707         isl_aff_free(aff);
 708         isl_mat_free(div);
 709         return NULL;
 710 }
 711
 712 /* Add two affine expressions that live in the same local space.
 713  */
 714 static __isl_give isl_aff *add_expanded(__isl_take isl_aff *aff1,
 715         __isl_take isl_aff *aff2)
 716 {
 717         isl_int gcd, f;
 718
 719         aff1 = isl_aff_cow(aff1);
 720         if (!aff1 || !aff2)
 721                 goto error;
 722
 723         aff1->v = isl_vec_cow(aff1->v);
 724         if (!aff1->v)
 725                 goto error;
 726
 727         isl_int_init(gcd);
 728         isl_int_init(f);
 729         isl_int_gcd(gcd, aff1->v->el[0], aff2->v->el[0]);
 730         isl_int_divexact(f, aff2->v->el[0], gcd);
 731         isl_seq_scale(aff1->v->el + 1, aff1->v->el + 1, f, aff1->v->size - 1);
 732         isl_int_divexact(f, aff1->v->el[0], gcd);
 733         isl_seq_addmul(aff1->v->el + 1, f, aff2->v->el + 1, aff1->v->size - 1);
 734         isl_int_divexact(f, aff2->v->el[0], gcd);
 735         isl_int_mul(aff1->v->el[0], aff1->v->el[0], f);
 736         isl_int_clear(f);
 737         isl_int_clear(gcd);
 738
 739         isl_aff_free(aff2);
 740         return aff1;
 741 error:
 742         isl_aff_free(aff1);
 743         isl_aff_free(aff2);
 744         return NULL;
 745 }
 746
 747 __isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
 748         __isl_take isl_aff *aff2)
 749 {
 750         isl_ctx *ctx;
 751         int *exp1 = NULL;
 752         int *exp2 = NULL;
 753         isl_mat *div;
 754
 755         if (!aff1 || !aff2)
 756                 goto error;
 757
 758         ctx = isl_aff_get_ctx(aff1);
 759         if (!isl_space_is_equal(aff1->ls->dim, aff2->ls->dim))
 760                 isl_die(ctx, isl_error_invalid,
 761                         "spaces don't match", goto error);
 762
 763         if (aff1->ls->div->n_row == 0 && aff2->ls->div->n_row == 0)
 764                 return add_expanded(aff1, aff2);
 765
 766         exp1 = isl_alloc_array(ctx, int, aff1->ls->div->n_row);
 767         exp2 = isl_alloc_array(ctx, int, aff2->ls->div->n_row);
 768         if (!exp1 || !exp2)
 769                 goto error;
 770
 771         div = isl_merge_divs(aff1->ls->div, aff2->ls->div, exp1, exp2);
 772         aff1 = isl_aff_expand_divs(aff1, isl_mat_copy(div), exp1);
 773         aff2 = isl_aff_expand_divs(aff2, div, exp2);
 774         free(exp1);
 775         free(exp2);
 776
 777         return add_expanded(aff1, aff2);
 778 error:
 779         free(exp1);
 780         free(exp2);
 781         isl_aff_free(aff1);
 782         isl_aff_free(aff2);
 783         return NULL;
 784 }
 785
 786 __isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
 787         __isl_take isl_aff *aff2)
 788 {
 789         return isl_aff_add(aff1, isl_aff_neg(aff2));
 790 }
 791
 792 __isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f)
 793 {
 794         isl_int gcd;
 795
 796         if (isl_int_is_one(f))
 797                 return aff;
 798
 799         aff = isl_aff_cow(aff);
 800         if (!aff)
 801                 return NULL;
 802         aff->v = isl_vec_cow(aff->v);
 803         if (!aff->v)
 804                 return isl_aff_free(aff);
 805
 806         isl_int_init(gcd);
 807         isl_int_gcd(gcd, aff->v->el[0], f);
 808         isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd);
 809         isl_int_divexact(gcd, f, gcd);
 810         isl_seq_scale(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
 811         isl_int_clear(gcd);
 812
 813         return aff;
 814 }
 815
 816 __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f)
 817 {
 818         isl_int gcd;
 819
 820         if (isl_int_is_one(f))
 821                 return aff;
 822
 823         aff = isl_aff_cow(aff);
 824         if (!aff)
 825                 return NULL;
 826         aff->v = isl_vec_cow(aff->v);
 827         if (!aff->v)
 828                 return isl_aff_free(aff);
 829
 830         isl_int_init(gcd);
 831         isl_seq_gcd(aff->v->el + 1, aff->v->size - 1, &gcd);
 832         isl_int_gcd(gcd, gcd, f);
 833         isl_seq_scale_down(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
 834         isl_int_divexact(gcd, f, gcd);
 835         isl_int_mul(aff->v->el[0], aff->v->el[0], gcd);
 836         isl_int_clear(gcd);
 837
 838         return aff;
 839 }
 840
 841 __isl_give isl_aff *isl_aff_scale_down_ui(__isl_take isl_aff *aff, unsigned f)
 842 {
 843         isl_int v;
 844
 845         if (f == 1)
 846                 return aff;
 847
 848         isl_int_init(v);
 849         isl_int_set_ui(v, f);
 850         aff = isl_aff_scale_down(aff, v);
 851         isl_int_clear(v);
 852
 853         return aff;
 854 }
 855
 856 __isl_give isl_aff *isl_aff_set_dim_name(__isl_take isl_aff *aff,
 857         enum isl_dim_type type, unsigned pos, const char *s)
 858 {
 859         aff = isl_aff_cow(aff);
 860         if (!aff)
 861                 return NULL;
 862         if (type == isl_dim_out)
 863                 isl_die(aff->v->ctx, isl_error_invalid,
 864                         "cannot set name of output/set dimension",
 865                         return isl_aff_free(aff));
 866         if (type == isl_dim_in)
 867                 type = isl_dim_set;
 868         aff->ls = isl_local_space_set_dim_name(aff->ls, type, pos, s);
 869         if (!aff->ls)
 870                 return isl_aff_free(aff);
 871
 872         return aff;
 873 }
 874
 875 __isl_give isl_aff *isl_aff_set_dim_id(__isl_take isl_aff *aff,
 876         enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
 877 {
 878         aff = isl_aff_cow(aff);
 879         if (!aff)
 880                 return isl_id_free(id);
 881         if (type == isl_dim_out)
 882                 isl_die(aff->v->ctx, isl_error_invalid,
 883                         "cannot set name of output/set dimension",
 884                         goto error);
 885         if (type == isl_dim_in)
 886                 type = isl_dim_set;
 887         aff->ls = isl_local_space_set_dim_id(aff->ls, type, pos, id);
 888         if (!aff->ls)
 889                 return isl_aff_free(aff);
 890
 891         return aff;
 892 error:
 893         isl_id_free(id);
 894         isl_aff_free(aff);
 895         return NULL;
 896 }
 897
 898 /* Exploit the equalities in "eq" to simplify the affine expression
 899  * and the expressions of the integer divisions in the local space.
 900  * The integer divisions in this local space are assumed to appear
 901  * as regular dimensions in "eq".
 902  */
 903 static __isl_give isl_aff *isl_aff_substitute_equalities_lifted(
 904         __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
 905 {
 906         int i, j;
 907         unsigned total;
 908         unsigned n_div;
 909
 910         if (!eq)
 911                 goto error;
 912         if (eq->n_eq == 0) {
 913                 isl_basic_set_free(eq);
 914                 return aff;
 915         }
 916
 917         aff = isl_aff_cow(aff);
 918         if (!aff)
 919                 goto error;
 920
 921         aff->ls = isl_local_space_substitute_equalities(aff->ls,
 922                                                         isl_basic_set_copy(eq));
 923         if (!aff->ls)
 924                 goto error;
 925
 926         total = 1 + isl_space_dim(eq->dim, isl_dim_all);
 927         n_div = eq->n_div;
 928         for (i = 0; i < eq->n_eq; ++i) {
 929                 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
 930                 if (j < 0 || j == 0 || j >= total)
 931                         continue;
 932
 933                 isl_seq_elim(aff->v->el + 1, eq->eq[i], j, total,
 934                                 &aff->v->el[0]);
 935         }
 936
 937         isl_basic_set_free(eq);
 938         return aff;
 939 error:
 940         isl_basic_set_free(eq);
 941         isl_aff_free(aff);
 942         return NULL;
 943 }
 944
 945 /* Exploit the equalities in "eq" to simplify the affine expression
 946  * and the expressions of the integer divisions in the local space.
 947  */
 948 static __isl_give isl_aff *isl_aff_substitute_equalities(
 949         __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
 950 {
 951         int n_div;
 952
 953         if (!aff || !eq)
 954                 goto error;
 955         n_div = isl_local_space_dim(aff->ls, isl_dim_div);
 956         if (n_div > 0)
 957                 eq = isl_basic_set_add(eq, isl_dim_set, n_div);
 958         return isl_aff_substitute_equalities_lifted(aff, eq);
 959 error:
 960         isl_basic_set_free(eq);
 961         isl_aff_free(aff);
 962         return NULL;
 963 }
 964
 965 /* Look for equalities among the variables shared by context and aff
 966  * and the integer divisions of aff, if any.
 967  * The equalities are then used to eliminate coefficients and/or integer
 968  * divisions from aff.
 969  */
 970 __isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff,
 971         __isl_take isl_set *context)
 972 {
 973         isl_basic_set *hull;
 974         int n_div;
 975
 976         if (!aff)
 977                 goto error;
 978         n_div = isl_local_space_dim(aff->ls, isl_dim_div);
 979         if (n_div > 0) {
 980                 isl_basic_set *bset;
 981                 isl_local_space *ls;
 982                 context = isl_set_add_dims(context, isl_dim_set, n_div);
 983                 ls = isl_aff_get_domain_local_space(aff);
 984                 bset = isl_basic_set_from_local_space(ls);
 985                 bset = isl_basic_set_lift(bset);
 986                 bset = isl_basic_set_flatten(bset);
 987                 context = isl_set_intersect(context,
 988                                             isl_set_from_basic_set(bset));
 989         }
 990
 991         hull = isl_set_affine_hull(context);
 992         return isl_aff_substitute_equalities_lifted(aff, hull);
 993 error:
 994         isl_aff_free(aff);
 995         isl_set_free(context);
 996         return NULL;
 997 }
 998
 999 /* Return a basic set containing those elements in the space
1000  * of aff where it is non-negative.
1001  */
1002 __isl_give isl_basic_set *isl_aff_nonneg_basic_set(__isl_take isl_aff *aff)
1003 {
1004         isl_constraint *ineq;
1005
1006         ineq = isl_inequality_from_aff(aff);
1007
1008         return isl_basic_set_from_constraint(ineq);
1009 }
1010
1011 /* Return a basic set containing those elements in the space
1012  * of aff where it is zero.
1013  */
1014 __isl_give isl_basic_set *isl_aff_zero_basic_set(__isl_take isl_aff *aff)
1015 {
1016         isl_constraint *ineq;
1017
1018         ineq = isl_equality_from_aff(aff);
1019
1020         return isl_basic_set_from_constraint(ineq);
1021 }
1022
1023 /* Return a basic set containing those elements in the shared space
1024  * of aff1 and aff2 where aff1 is greater than or equal to aff2.
1025  */
1026 __isl_give isl_basic_set *isl_aff_ge_basic_set(__isl_take isl_aff *aff1,
1027         __isl_take isl_aff *aff2)
1028 {
1029         aff1 = isl_aff_sub(aff1, aff2);
1030
1031         return isl_aff_nonneg_basic_set(aff1);
1032 }
1033
1034 /* Return a basic set containing those elements in the shared space
1035  * of aff1 and aff2 where aff1 is smaller than or equal to aff2.
1036  */
1037 __isl_give isl_basic_set *isl_aff_le_basic_set(__isl_take isl_aff *aff1,
1038         __isl_take isl_aff *aff2)
1039 {
1040         return isl_aff_ge_basic_set(aff2, aff1);
1041 }
1042
1043 __isl_give isl_aff *isl_aff_add_on_domain(__isl_keep isl_set *dom,
1044         __isl_take isl_aff *aff1, __isl_take isl_aff *aff2)
1045 {
1046         aff1 = isl_aff_add(aff1, aff2);
1047         aff1 = isl_aff_gist(aff1, isl_set_copy(dom));
1048         return aff1;
1049 }
1050
1051 int isl_aff_is_empty(__isl_keep isl_aff *aff)
1052 {
1053         if (!aff)
1054                 return -1;
1055
1056         return 0;
1057 }
1058
1059 /* Check whether the given affine expression has non-zero coefficient
1060  * for any dimension in the given range or if any of these dimensions
1061  * appear with non-zero coefficients in any of the integer divisions
1062  * involved in the affine expression.
1063  */
1064 int isl_aff_involves_dims(__isl_keep isl_aff *aff,
1065         enum isl_dim_type type, unsigned first, unsigned n)
1066 {
1067         int i;
1068         isl_ctx *ctx;
1069         int *active = NULL;
1070         int involves = 0;
1071
1072         if (!aff)
1073                 return -1;
1074         if (n == 0)
1075                 return 0;
1076
1077         ctx = isl_aff_get_ctx(aff);
1078         if (first + n > isl_aff_dim(aff, type))
1079                 isl_die(ctx, isl_error_invalid,
1080                         "range out of bounds", return -1);
1081
1082         active = isl_local_space_get_active(aff->ls, aff->v->el + 2);
1083         if (!active)
1084                 goto error;
1085
1086         first += isl_local_space_offset(aff->ls, type) - 1;
1087         for (i = 0; i < n; ++i)
1088                 if (active[first + i]) {
1089                         involves = 1;
1090                         break;
1091                 }
1092
1093         free(active);
1094
1095         return involves;
1096 error:
1097         free(active);
1098         return -1;
1099 }
1100
1101 __isl_give isl_aff *isl_aff_drop_dims(__isl_take isl_aff *aff,
1102         enum isl_dim_type type, unsigned first, unsigned n)
1103 {
1104         isl_ctx *ctx;
1105
1106         if (!aff)
1107                 return NULL;
1108         if (type == isl_dim_out)
1109                 isl_die(aff->v->ctx, isl_error_invalid,
1110                         "cannot drop output/set dimension",
1111                         return isl_aff_free(aff));
1112         if (type == isl_dim_in)
1113                 type = isl_dim_set;
1114         if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
1115                 return aff;
1116
1117         ctx = isl_aff_get_ctx(aff);
1118         if (first + n > isl_local_space_dim(aff->ls, type))
1119                 isl_die(ctx, isl_error_invalid, "range out of bounds",
1120                         return isl_aff_free(aff));
1121
1122         aff = isl_aff_cow(aff);
1123         if (!aff)
1124                 return NULL;
1125
1126         aff->ls = isl_local_space_drop_dims(aff->ls, type, first, n);
1127         if (!aff->ls)
1128                 return isl_aff_free(aff);
1129
1130         first += 1 + isl_local_space_offset(aff->ls, type);
1131         aff->v = isl_vec_drop_els(aff->v, first, n);
1132         if (!aff->v)
1133                 return isl_aff_free(aff);
1134
1135         return aff;
1136 }
1137
1138 __isl_give isl_aff *isl_aff_insert_dims(__isl_take isl_aff *aff,
1139         enum isl_dim_type type, unsigned first, unsigned n)
1140 {
1141         isl_ctx *ctx;
1142
1143         if (!aff)
1144                 return NULL;
1145         if (type == isl_dim_out)
1146                 isl_die(aff->v->ctx, isl_error_invalid,
1147                         "cannot insert output/set dimensions",
1148                         return isl_aff_free(aff));
1149         if (type == isl_dim_in)
1150                 type = isl_dim_set;
1151         if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
1152                 return aff;
1153
1154         ctx = isl_aff_get_ctx(aff);
1155         if (first > isl_local_space_dim(aff->ls, type))
1156                 isl_die(ctx, isl_error_invalid, "position out of bounds",
1157                         return isl_aff_free(aff));
1158
1159         aff = isl_aff_cow(aff);
1160         if (!aff)
1161                 return NULL;
1162
1163         aff->ls = isl_local_space_insert_dims(aff->ls, type, first, n);
1164         if (!aff->ls)
1165                 return isl_aff_free(aff);
1166
1167         first += 1 + isl_local_space_offset(aff->ls, type);
1168         aff->v = isl_vec_insert_zero_els(aff->v, first, n);
1169         if (!aff->v)
1170                 return isl_aff_free(aff);
1171
1172         return aff;
1173 }
1174
1175 __isl_give isl_aff *isl_aff_add_dims(__isl_take isl_aff *aff,
1176         enum isl_dim_type type, unsigned n)
1177 {
1178         unsigned pos;
1179
1180         pos = isl_aff_dim(aff, type);
1181
1182         return isl_aff_insert_dims(aff, type, pos, n);
1183 }
1184
1185 __isl_give isl_pw_aff *isl_pw_aff_add_dims(__isl_take isl_pw_aff *pwaff,
1186         enum isl_dim_type type, unsigned n)
1187 {
1188         unsigned pos;
1189
1190         pos = isl_pw_aff_dim(pwaff, type);
1191
1192         return isl_pw_aff_insert_dims(pwaff, type, pos, n);
1193 }
1194
1195 __isl_give isl_pw_aff *isl_pw_aff_from_aff(__isl_take isl_aff *aff)
1196 {
1197         isl_set *dom = isl_set_universe(isl_aff_get_domain_space(aff));
1198         return isl_pw_aff_alloc(dom, aff);
1199 }
1200
1201 #undef PW
1202 #define PW isl_pw_aff
1203 #undef EL
1204 #define EL isl_aff
1205 #undef EL_IS_ZERO
1206 #define EL_IS_ZERO is_empty
1207 #undef ZERO
1208 #define ZERO empty
1209 #undef IS_ZERO
1210 #define IS_ZERO is_empty
1211 #undef FIELD
1212 #define FIELD aff
1213
1214 #define NO_EVAL
1215 #define NO_OPT
1216 #define NO_MOVE_DIMS
1217 #define NO_LIFT
1218 #define NO_MORPH
1219
1220 #include <isl_pw_templ.c>
1221
1222 static __isl_give isl_set *align_params_pw_pw_set_and(
1223         __isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2,
1224         __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1225                                     __isl_take isl_pw_aff *pwaff2))
1226 {
1227         if (!pwaff1 || !pwaff2)
1228                 goto error;
1229         if (isl_space_match(pwaff1->dim, isl_dim_param,
1230                           pwaff2->dim, isl_dim_param))
1231                 return fn(pwaff1, pwaff2);
1232         if (!isl_space_has_named_params(pwaff1->dim) ||
1233             !isl_space_has_named_params(pwaff2->dim))
1234                 isl_die(isl_pw_aff_get_ctx(pwaff1), isl_error_invalid,
1235                         "unaligned unnamed parameters", goto error);
1236         pwaff1 = isl_pw_aff_align_params(pwaff1, isl_pw_aff_get_space(pwaff2));
1237         pwaff2 = isl_pw_aff_align_params(pwaff2, isl_pw_aff_get_space(pwaff1));
1238         return fn(pwaff1, pwaff2);
1239 error:
1240         isl_pw_aff_free(pwaff1);
1241         isl_pw_aff_free(pwaff2);
1242         return NULL;
1243 }
1244
1245 /* Compute a piecewise quasi-affine expression with a domain that
1246  * is the union of those of pwaff1 and pwaff2 and such that on each
1247  * cell, the quasi-affine expression is the better (according to cmp)
1248  * of those of pwaff1 and pwaff2.  If only one of pwaff1 or pwaff2
1249  * is defined on a given cell, then the associated expression
1250  * is the defined one.
1251  */
1252 static __isl_give isl_pw_aff *pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1253         __isl_take isl_pw_aff *pwaff2,
1254         __isl_give isl_basic_set *(*cmp)(__isl_take isl_aff *aff1,
1255                                         __isl_take isl_aff *aff2))
1256 {
1257         int i, j, n;
1258         isl_pw_aff *res;
1259         isl_ctx *ctx;
1260         isl_set *set;
1261
1262         if (!pwaff1 || !pwaff2)
1263                 goto error;
1264
1265         ctx = isl_space_get_ctx(pwaff1->dim);
1266         if (!isl_space_is_equal(pwaff1->dim, pwaff2->dim))
1267                 isl_die(ctx, isl_error_invalid,
1268                         "arguments should live in same space", goto error);
1269
1270         if (isl_pw_aff_is_empty(pwaff1)) {
1271                 isl_pw_aff_free(pwaff1);
1272                 return pwaff2;
1273         }
1274
1275         if (isl_pw_aff_is_empty(pwaff2)) {
1276                 isl_pw_aff_free(pwaff2);
1277                 return pwaff1;
1278         }
1279
1280         n = 2 * (pwaff1->n + 1) * (pwaff2->n + 1);
1281         res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n);
1282
1283         for (i = 0; i < pwaff1->n; ++i) {
1284                 set = isl_set_copy(pwaff1->p[i].set);
1285                 for (j = 0; j < pwaff2->n; ++j) {
1286                         struct isl_set *common;
1287                         isl_set *better;
1288
1289                         common = isl_set_intersect(
1290                                         isl_set_copy(pwaff1->p[i].set),
1291                                         isl_set_copy(pwaff2->p[j].set));
1292                         better = isl_set_from_basic_set(cmp(
1293                                         isl_aff_copy(pwaff2->p[j].aff),
1294                                         isl_aff_copy(pwaff1->p[i].aff)));
1295                         better = isl_set_intersect(common, better);
1296                         if (isl_set_plain_is_empty(better)) {
1297                                 isl_set_free(better);
1298                                 continue;
1299                         }
1300                         set = isl_set_subtract(set, isl_set_copy(better));
1301
1302                         res = isl_pw_aff_add_piece(res, better,
1303                                                 isl_aff_copy(pwaff2->p[j].aff));
1304                 }
1305                 res = isl_pw_aff_add_piece(res, set,
1306                                                 isl_aff_copy(pwaff1->p[i].aff));
1307         }
1308
1309         for (j = 0; j < pwaff2->n; ++j) {
1310                 set = isl_set_copy(pwaff2->p[j].set);
1311                 for (i = 0; i < pwaff1->n; ++i)
1312                         set = isl_set_subtract(set,
1313                                         isl_set_copy(pwaff1->p[i].set));
1314                 res = isl_pw_aff_add_piece(res, set,
1315                                                 isl_aff_copy(pwaff2->p[j].aff));
1316         }
1317
1318         isl_pw_aff_free(pwaff1);
1319         isl_pw_aff_free(pwaff2);
1320
1321         return res;
1322 error:
1323         isl_pw_aff_free(pwaff1);
1324         isl_pw_aff_free(pwaff2);
1325         return NULL;
1326 }
1327
1328 /* Compute a piecewise quasi-affine expression with a domain that
1329  * is the union of those of pwaff1 and pwaff2 and such that on each
1330  * cell, the quasi-affine expression is the maximum of those of pwaff1
1331  * and pwaff2.  If only one of pwaff1 or pwaff2 is defined on a given
1332  * cell, then the associated expression is the defined one.
1333  */
1334 static __isl_give isl_pw_aff *pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1335         __isl_take isl_pw_aff *pwaff2)
1336 {
1337         return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_ge_basic_set);
1338 }
1339
1340 __isl_give isl_pw_aff *isl_pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1341         __isl_take isl_pw_aff *pwaff2)
1342 {
1343         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2,
1344                                                         &pw_aff_union_max);
1345 }
1346
1347 /* Compute a piecewise quasi-affine expression with a domain that
1348  * is the union of those of pwaff1 and pwaff2 and such that on each
1349  * cell, the quasi-affine expression is the minimum of those of pwaff1
1350  * and pwaff2.  If only one of pwaff1 or pwaff2 is defined on a given
1351  * cell, then the associated expression is the defined one.
1352  */
1353 static __isl_give isl_pw_aff *pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1354         __isl_take isl_pw_aff *pwaff2)
1355 {
1356         return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_le_basic_set);
1357 }
1358
1359 __isl_give isl_pw_aff *isl_pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1360         __isl_take isl_pw_aff *pwaff2)
1361 {
1362         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2,
1363                                                         &pw_aff_union_min);
1364 }
1365
1366 __isl_give isl_pw_aff *isl_pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1367         __isl_take isl_pw_aff *pwaff2, int max)
1368 {
1369         if (max)
1370                 return isl_pw_aff_union_max(pwaff1, pwaff2);
1371         else
1372                 return isl_pw_aff_union_min(pwaff1, pwaff2);
1373 }
1374
1375 /* Construct a map with as domain the domain of pwaff and
1376  * one-dimensional range corresponding to the affine expressions.
1377  */
1378 static __isl_give isl_map *map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1379 {
1380         int i;
1381         isl_space *dim;
1382         isl_map *map;
1383
1384         if (!pwaff)
1385                 return NULL;
1386
1387         dim = isl_pw_aff_get_space(pwaff);
1388         map = isl_map_empty(dim);
1389
1390         for (i = 0; i < pwaff->n; ++i) {
1391                 isl_basic_map *bmap;
1392                 isl_map *map_i;
1393
1394                 bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
1395                 map_i = isl_map_from_basic_map(bmap);
1396                 map_i = isl_map_intersect_domain(map_i,
1397                                                 isl_set_copy(pwaff->p[i].set));
1398                 map = isl_map_union_disjoint(map, map_i);
1399         }
1400
1401         isl_pw_aff_free(pwaff);
1402
1403         return map;
1404 }
1405
1406 /* Construct a map with as domain the domain of pwaff and
1407  * one-dimensional range corresponding to the affine expressions.
1408  */
1409 __isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1410 {
1411         if (isl_space_is_set(pwaff->dim))
1412                 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1413                         "space of input is not a map",
1414                         return isl_pw_aff_free(pwaff));
1415         return map_from_pw_aff(pwaff);
1416 }
1417
1418 /* Construct a one-dimensional set with as parameter domain
1419  * the domain of pwaff and the single set dimension
1420  * corresponding to the affine expressions.
1421  */
1422 __isl_give isl_set *isl_set_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1423 {
1424         if (!isl_space_is_set(pwaff->dim))
1425                 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1426                         "space of input is not a set",
1427                         return isl_pw_aff_free(pwaff));
1428         return map_from_pw_aff(pwaff);
1429 }
1430
1431 /* Return a set containing those elements in the domain
1432  * of pwaff where it is non-negative.
1433  */
1434 __isl_give isl_set *isl_pw_aff_nonneg_set(__isl_take isl_pw_aff *pwaff)
1435 {
1436         int i;
1437         isl_set *set;
1438
1439         if (!pwaff)
1440                 return NULL;
1441
1442         set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1443
1444         for (i = 0; i < pwaff->n; ++i) {
1445                 isl_basic_set *bset;
1446                 isl_set *set_i;
1447
1448                 bset = isl_aff_nonneg_basic_set(isl_aff_copy(pwaff->p[i].aff));
1449                 set_i = isl_set_from_basic_set(bset);
1450                 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1451                 set = isl_set_union_disjoint(set, set_i);
1452         }
1453
1454         isl_pw_aff_free(pwaff);
1455
1456         return set;
1457 }
1458
1459 /* Return a set containing those elements in the domain
1460  * of pwaff where it is zero.
1461  */
1462 __isl_give isl_set *isl_pw_aff_zero_set(__isl_take isl_pw_aff *pwaff)
1463 {
1464         int i;
1465         isl_set *set;
1466
1467         if (!pwaff)
1468                 return NULL;
1469
1470         set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1471
1472         for (i = 0; i < pwaff->n; ++i) {
1473                 isl_basic_set *bset;
1474                 isl_set *set_i;
1475
1476                 bset = isl_aff_zero_basic_set(isl_aff_copy(pwaff->p[i].aff));
1477                 set_i = isl_set_from_basic_set(bset);
1478                 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1479                 set = isl_set_union_disjoint(set, set_i);
1480         }
1481
1482         isl_pw_aff_free(pwaff);
1483
1484         return set;
1485 }
1486
1487 /* Return a set containing those elements in the domain
1488  * of pwaff where it is not zero.
1489  */
1490 __isl_give isl_set *isl_pw_aff_non_zero_set(__isl_take isl_pw_aff *pwaff)
1491 {
1492         return isl_set_complement(isl_pw_aff_zero_set(pwaff));
1493 }
1494
1495 /* Return a set containing those elements in the shared domain
1496  * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
1497  *
1498  * We compute the difference on the shared domain and then construct
1499  * the set of values where this difference is non-negative.
1500  * If strict is set, we first subtract 1 from the difference.
1501  * If equal is set, we only return the elements where pwaff1 and pwaff2
1502  * are equal.
1503  */
1504 static __isl_give isl_set *pw_aff_gte_set(__isl_take isl_pw_aff *pwaff1,
1505         __isl_take isl_pw_aff *pwaff2, int strict, int equal)
1506 {
1507         isl_set *set1, *set2;
1508
1509         set1 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff1));
1510         set2 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff2));
1511         set1 = isl_set_intersect(set1, set2);
1512         pwaff1 = isl_pw_aff_intersect_domain(pwaff1, isl_set_copy(set1));
1513         pwaff2 = isl_pw_aff_intersect_domain(pwaff2, isl_set_copy(set1));
1514         pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_neg(pwaff2));
1515
1516         if (strict) {
1517                 isl_space *dim = isl_set_get_space(set1);
1518                 isl_aff *aff;
1519                 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
1520                 aff = isl_aff_add_constant_si(aff, -1);
1521                 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_alloc(set1, aff));
1522         } else
1523                 isl_set_free(set1);
1524
1525         if (equal)
1526                 return isl_pw_aff_zero_set(pwaff1);
1527         return isl_pw_aff_nonneg_set(pwaff1);
1528 }
1529
1530 /* Return a set containing those elements in the shared domain
1531  * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
1532  */
1533 static __isl_give isl_set *pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1534         __isl_take isl_pw_aff *pwaff2)
1535 {
1536         return pw_aff_gte_set(pwaff1, pwaff2, 0, 1);
1537 }
1538
1539 __isl_give isl_set *isl_pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1540         __isl_take isl_pw_aff *pwaff2)
1541 {
1542         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_eq_set);
1543 }
1544
1545 /* Return a set containing those elements in the shared domain
1546  * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
1547  */
1548 static __isl_give isl_set *pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1549         __isl_take isl_pw_aff *pwaff2)
1550 {
1551         return pw_aff_gte_set(pwaff1, pwaff2, 0, 0);
1552 }
1553
1554 __isl_give isl_set *isl_pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1555         __isl_take isl_pw_aff *pwaff2)
1556 {
1557         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ge_set);
1558 }
1559
1560 /* Return a set containing those elements in the shared domain
1561  * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
1562  */
1563 static __isl_give isl_set *pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1564         __isl_take isl_pw_aff *pwaff2)
1565 {
1566         return pw_aff_gte_set(pwaff1, pwaff2, 1, 0);
1567 }
1568
1569 __isl_give isl_set *isl_pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1570         __isl_take isl_pw_aff *pwaff2)
1571 {
1572         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_gt_set);
1573 }
1574
1575 __isl_give isl_set *isl_pw_aff_le_set(__isl_take isl_pw_aff *pwaff1,
1576         __isl_take isl_pw_aff *pwaff2)
1577 {
1578         return isl_pw_aff_ge_set(pwaff2, pwaff1);
1579 }
1580
1581 __isl_give isl_set *isl_pw_aff_lt_set(__isl_take isl_pw_aff *pwaff1,
1582         __isl_take isl_pw_aff *pwaff2)
1583 {
1584         return isl_pw_aff_gt_set(pwaff2, pwaff1);
1585 }
1586
1587 /* Return a set containing those elements in the shared domain
1588  * of the elements of list1 and list2 where each element in list1
1589  * has the relation specified by "fn" with each element in list2.
1590  */
1591 static __isl_give isl_set *pw_aff_list_set(__isl_take isl_pw_aff_list *list1,
1592         __isl_take isl_pw_aff_list *list2,
1593         __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1594                                     __isl_take isl_pw_aff *pwaff2))
1595 {
1596         int i, j;
1597         isl_ctx *ctx;
1598         isl_set *set;
1599
1600         if (!list1 || !list2)
1601                 goto error;
1602
1603         ctx = isl_pw_aff_list_get_ctx(list1);
1604         if (list1->n < 1 || list2->n < 1)
1605                 isl_die(ctx, isl_error_invalid,
1606                         "list should contain at least one element", goto error);
1607
1608         set = isl_set_universe(isl_pw_aff_get_domain_space(list1->p[0]));
1609         for (i = 0; i < list1->n; ++i)
1610                 for (j = 0; j < list2->n; ++j) {
1611                         isl_set *set_ij;
1612
1613                         set_ij = fn(isl_pw_aff_copy(list1->p[i]),
1614                                     isl_pw_aff_copy(list2->p[j]));
1615                         set = isl_set_intersect(set, set_ij);
1616                 }
1617
1618         isl_pw_aff_list_free(list1);
1619         isl_pw_aff_list_free(list2);
1620         return set;
1621 error:
1622         isl_pw_aff_list_free(list1);
1623         isl_pw_aff_list_free(list2);
1624         return NULL;
1625 }
1626
1627 /* Return a set containing those elements in the shared domain
1628  * of the elements of list1 and list2 where each element in list1
1629  * is equal to each element in list2.
1630  */
1631 __isl_give isl_set *isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list *list1,
1632         __isl_take isl_pw_aff_list *list2)
1633 {
1634         return pw_aff_list_set(list1, list2, &isl_pw_aff_eq_set);
1635 }
1636
1637 __isl_give isl_set *isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list *list1,
1638         __isl_take isl_pw_aff_list *list2)
1639 {
1640         return pw_aff_list_set(list1, list2, &isl_pw_aff_ne_set);
1641 }
1642
1643 /* Return a set containing those elements in the shared domain
1644  * of the elements of list1 and list2 where each element in list1
1645  * is less than or equal to each element in list2.
1646  */
1647 __isl_give isl_set *isl_pw_aff_list_le_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_le_set);
1651 }
1652
1653 __isl_give isl_set *isl_pw_aff_list_lt_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_lt_set);
1657 }
1658
1659 __isl_give isl_set *isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list *list1,
1660         __isl_take isl_pw_aff_list *list2)
1661 {
1662         return pw_aff_list_set(list1, list2, &isl_pw_aff_ge_set);
1663 }
1664
1665 __isl_give isl_set *isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list *list1,
1666         __isl_take isl_pw_aff_list *list2)
1667 {
1668         return pw_aff_list_set(list1, list2, &isl_pw_aff_gt_set);
1669 }
1670
1671
1672 /* Return a set containing those elements in the shared domain
1673  * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
1674  */
1675 static __isl_give isl_set *pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1676         __isl_take isl_pw_aff *pwaff2)
1677 {
1678         isl_set *set_lt, *set_gt;
1679
1680         set_lt = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1),
1681                                    isl_pw_aff_copy(pwaff2));
1682         set_gt = isl_pw_aff_gt_set(pwaff1, pwaff2);
1683         return isl_set_union_disjoint(set_lt, set_gt);
1684 }
1685
1686 __isl_give isl_set *isl_pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1687         __isl_take isl_pw_aff *pwaff2)
1688 {
1689         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ne_set);
1690 }
1691
1692 __isl_give isl_pw_aff *isl_pw_aff_scale_down(__isl_take isl_pw_aff *pwaff,
1693         isl_int v)
1694 {
1695         int i;
1696
1697         if (isl_int_is_one(v))
1698                 return pwaff;
1699         if (!isl_int_is_pos(v))
1700                 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1701                         "factor needs to be positive",
1702                         return isl_pw_aff_free(pwaff));
1703         pwaff = isl_pw_aff_cow(pwaff);
1704         if (!pwaff)
1705                 return NULL;
1706         if (pwaff->n == 0)
1707                 return pwaff;
1708
1709         for (i = 0; i < pwaff->n; ++i) {
1710                 pwaff->p[i].aff = isl_aff_scale_down(pwaff->p[i].aff, v);
1711                 if (!pwaff->p[i].aff)
1712                         return isl_pw_aff_free(pwaff);
1713         }
1714
1715         return pwaff;
1716 }
1717
1718 __isl_give isl_pw_aff *isl_pw_aff_floor(__isl_take isl_pw_aff *pwaff)
1719 {
1720         int i;
1721
1722         pwaff = isl_pw_aff_cow(pwaff);
1723         if (!pwaff)
1724                 return NULL;
1725         if (pwaff->n == 0)
1726                 return pwaff;
1727
1728         for (i = 0; i < pwaff->n; ++i) {
1729                 pwaff->p[i].aff = isl_aff_floor(pwaff->p[i].aff);
1730                 if (!pwaff->p[i].aff)
1731                         return isl_pw_aff_free(pwaff);
1732         }
1733
1734         return pwaff;
1735 }
1736
1737 __isl_give isl_pw_aff *isl_pw_aff_ceil(__isl_take isl_pw_aff *pwaff)
1738 {
1739         int i;
1740
1741         pwaff = isl_pw_aff_cow(pwaff);
1742         if (!pwaff)
1743                 return NULL;
1744         if (pwaff->n == 0)
1745                 return pwaff;
1746
1747         for (i = 0; i < pwaff->n; ++i) {
1748                 pwaff->p[i].aff = isl_aff_ceil(pwaff->p[i].aff);
1749                 if (!pwaff->p[i].aff)
1750                         return isl_pw_aff_free(pwaff);
1751         }
1752
1753         return pwaff;
1754 }
1755
1756 /* Return an affine expression that is equal to pwaff_true for elements
1757  * in "cond" and to pwaff_false for elements not in "cond".
1758  * That is, return cond ? pwaff_true : pwaff_false;
1759  */
1760 __isl_give isl_pw_aff *isl_pw_aff_cond(__isl_take isl_set *cond,
1761         __isl_take isl_pw_aff *pwaff_true, __isl_take isl_pw_aff *pwaff_false)
1762 {
1763         isl_set *comp;
1764
1765         comp = isl_set_complement(isl_set_copy(cond));
1766         pwaff_true = isl_pw_aff_intersect_domain(pwaff_true, cond);
1767         pwaff_false = isl_pw_aff_intersect_domain(pwaff_false, comp);
1768
1769         return isl_pw_aff_add_disjoint(pwaff_true, pwaff_false);
1770 }
1771
1772 int isl_aff_is_cst(__isl_keep isl_aff *aff)
1773 {
1774         if (!aff)
1775                 return -1;
1776
1777         return isl_seq_first_non_zero(aff->v->el + 2, aff->v->size - 2) == -1;
1778 }
1779
1780 /* Check whether pwaff is a piecewise constant.
1781  */
1782 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff)
1783 {
1784         int i;
1785
1786         if (!pwaff)
1787                 return -1;
1788
1789         for (i = 0; i < pwaff->n; ++i) {
1790                 int is_cst = isl_aff_is_cst(pwaff->p[i].aff);
1791                 if (is_cst < 0 || !is_cst)
1792                         return is_cst;
1793         }
1794
1795         return 1;
1796 }
1797
1798 __isl_give isl_aff *isl_aff_mul(__isl_take isl_aff *aff1,
1799         __isl_take isl_aff *aff2)
1800 {
1801         if (!isl_aff_is_cst(aff2) && isl_aff_is_cst(aff1))
1802                 return isl_aff_mul(aff2, aff1);
1803
1804         if (!isl_aff_is_cst(aff2))
1805                 isl_die(isl_aff_get_ctx(aff1), isl_error_invalid,
1806                         "at least one affine expression should be constant",
1807                         goto error);
1808
1809         aff1 = isl_aff_cow(aff1);
1810         if (!aff1 || !aff2)
1811                 goto error;
1812
1813         aff1 = isl_aff_scale(aff1, aff2->v->el[1]);
1814         aff1 = isl_aff_scale_down(aff1, aff2->v->el[0]);
1815
1816         isl_aff_free(aff2);
1817         return aff1;
1818 error:
1819         isl_aff_free(aff1);
1820         isl_aff_free(aff2);
1821         return NULL;
1822 }
1823
1824 static __isl_give isl_pw_aff *pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
1825         __isl_take isl_pw_aff *pwaff2)
1826 {
1827         int i, j, n;
1828         isl_pw_aff *res;
1829
1830         if (!pwaff1 || !pwaff2)
1831                 goto error;
1832
1833         n = pwaff1->n * pwaff2->n;
1834         res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n);
1835
1836         for (i = 0; i < pwaff1->n; ++i) {
1837                 for (j = 0; j < pwaff2->n; ++j) {
1838                         isl_set *common;
1839                         isl_aff *prod;
1840                         common = isl_set_intersect(
1841                                         isl_set_copy(pwaff1->p[i].set),
1842                                         isl_set_copy(pwaff2->p[j].set));
1843                         if (isl_set_plain_is_empty(common)) {
1844                                 isl_set_free(common);
1845                                 continue;
1846                         }
1847
1848                         prod = isl_aff_mul(isl_aff_copy(pwaff1->p[i].aff),
1849                                             isl_aff_copy(pwaff2->p[j].aff));
1850
1851                         res = isl_pw_aff_add_piece(res, common, prod);
1852                 }
1853         }
1854
1855         isl_pw_aff_free(pwaff1);
1856         isl_pw_aff_free(pwaff2);
1857         return res;
1858 error:
1859         isl_pw_aff_free(pwaff1);
1860         isl_pw_aff_free(pwaff2);
1861         return NULL;
1862 }
1863
1864 __isl_give isl_pw_aff *isl_pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
1865         __isl_take isl_pw_aff *pwaff2)
1866 {
1867         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_mul);
1868 }
1869
1870 static __isl_give isl_pw_aff *pw_aff_min(__isl_take isl_pw_aff *pwaff1,
1871         __isl_take isl_pw_aff *pwaff2)
1872 {
1873         isl_set *le;
1874
1875         le = isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1),
1876                                 isl_pw_aff_copy(pwaff2));
1877         return isl_pw_aff_cond(le, pwaff1, pwaff2);
1878 }
1879
1880 __isl_give isl_pw_aff *isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1,
1881         __isl_take isl_pw_aff *pwaff2)
1882 {
1883         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_min);
1884 }
1885
1886 static __isl_give isl_pw_aff *pw_aff_max(__isl_take isl_pw_aff *pwaff1,
1887         __isl_take isl_pw_aff *pwaff2)
1888 {
1889         isl_set *le;
1890
1891         le = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1),
1892                                 isl_pw_aff_copy(pwaff2));
1893         return isl_pw_aff_cond(le, pwaff1, pwaff2);
1894 }
1895
1896 __isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1,
1897         __isl_take isl_pw_aff *pwaff2)
1898 {
1899         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_max);
1900 }
1901
1902 static __isl_give isl_pw_aff *pw_aff_list_reduce(
1903         __isl_take isl_pw_aff_list *list,
1904         __isl_give isl_pw_aff *(*fn)(__isl_take isl_pw_aff *pwaff1,
1905                                         __isl_take isl_pw_aff *pwaff2))
1906 {
1907         int i;
1908         isl_ctx *ctx;
1909         isl_pw_aff *res;
1910
1911         if (!list)
1912                 return NULL;
1913
1914         ctx = isl_pw_aff_list_get_ctx(list);
1915         if (list->n < 1)
1916                 isl_die(ctx, isl_error_invalid,
1917                         "list should contain at least one element",
1918                         return isl_pw_aff_list_free(list));
1919
1920         res = isl_pw_aff_copy(list->p[0]);
1921         for (i = 1; i < list->n; ++i)
1922                 res = fn(res, isl_pw_aff_copy(list->p[i]));
1923
1924         isl_pw_aff_list_free(list);
1925         return res;
1926 }
1927
1928 /* Return an isl_pw_aff that maps each element in the intersection of the
1929  * domains of the elements of list to the minimal corresponding affine
1930  * expression.
1931  */
1932 __isl_give isl_pw_aff *isl_pw_aff_list_min(__isl_take isl_pw_aff_list *list)
1933 {
1934         return pw_aff_list_reduce(list, &isl_pw_aff_min);
1935 }
1936
1937 /* Return an isl_pw_aff that maps each element in the intersection of the
1938  * domains of the elements of list to the maximal corresponding affine
1939  * expression.
1940  */
1941 __isl_give isl_pw_aff *isl_pw_aff_list_max(__isl_take isl_pw_aff_list *list)
1942 {
1943         return pw_aff_list_reduce(list, &isl_pw_aff_max);
1944 }
1945
1946 #undef BASE
1947 #define BASE aff
1948
1949 #include <isl_multi_templ.c>
1950
1951 __isl_give isl_multi_aff *isl_multi_aff_add(__isl_take isl_multi_aff *maff1,
1952         __isl_take isl_multi_aff *maff2)
1953 {
1954         int i;
1955         isl_ctx *ctx;
1956
1957         maff1 = isl_multi_aff_cow(maff1);
1958         if (!maff1 || !maff2)
1959                 goto error;
1960
1961         ctx = isl_multi_aff_get_ctx(maff1);
1962         if (!isl_space_is_equal(maff1->space, maff2->space))
1963                 isl_die(ctx, isl_error_invalid,
1964                         "spaces don't match", goto error);
1965
1966         for (i = 0; i < maff1->n; ++i) {
1967                 maff1->p[i] = isl_aff_add(maff1->p[i],
1968                                             isl_aff_copy(maff2->p[i]));
1969                 if (!maff1->p[i])
1970                         goto error;
1971         }
1972
1973         isl_multi_aff_free(maff2);
1974         return maff1;
1975 error:
1976         isl_multi_aff_free(maff1);
1977         isl_multi_aff_free(maff2);
1978         return NULL;
1979 }
1980
1981 /* Exploit the equalities in "eq" to simplify the affine expressions.
1982  */
1983 static __isl_give isl_multi_aff *isl_multi_aff_substitute_equalities(
1984         __isl_take isl_multi_aff *maff, __isl_take isl_basic_set *eq)
1985 {
1986         int i;
1987
1988         maff = isl_multi_aff_cow(maff);
1989         if (!maff || !eq)
1990                 goto error;
1991
1992         for (i = 0; i < maff->n; ++i) {
1993                 maff->p[i] = isl_aff_substitute_equalities(maff->p[i],
1994                                                     isl_basic_set_copy(eq));
1995                 if (!maff->p[i])
1996                         goto error;
1997         }
1998
1999         isl_basic_set_free(eq);
2000         return maff;
2001 error:
2002         isl_basic_set_free(eq);
2003         isl_multi_aff_free(maff);
2004         return NULL;
2005 }
2006
2007 __isl_give isl_multi_aff *isl_multi_aff_scale(__isl_take isl_multi_aff *maff,
2008         isl_int f)
2009 {
2010         int i;
2011
2012         maff = isl_multi_aff_cow(maff);
2013         if (!maff)
2014                 return NULL;
2015
2016         for (i = 0; i < maff->n; ++i) {
2017                 maff->p[i] = isl_aff_scale(maff->p[i], f);
2018                 if (!maff->p[i])
2019                         return isl_multi_aff_free(maff);
2020         }
2021
2022         return maff;
2023 }
2024
2025 __isl_give isl_multi_aff *isl_multi_aff_add_on_domain(__isl_keep isl_set *dom,
2026         __isl_take isl_multi_aff *maff1, __isl_take isl_multi_aff *maff2)
2027 {
2028         maff1 = isl_multi_aff_add(maff1, maff2);
2029         maff1 = isl_multi_aff_gist(maff1, isl_set_copy(dom));
2030         return maff1;
2031 }
2032
2033 int isl_multi_aff_is_empty(__isl_keep isl_multi_aff *maff)
2034 {
2035         if (!maff)
2036                 return -1;
2037
2038         return 0;
2039 }
2040
2041 int isl_multi_aff_plain_is_equal(__isl_keep isl_multi_aff *maff1,
2042         __isl_keep isl_multi_aff *maff2)
2043 {
2044         int i;
2045         int equal;
2046
2047         if (!maff1 || !maff2)
2048                 return -1;
2049         if (maff1->n != maff2->n)
2050                 return 0;
2051         equal = isl_space_is_equal(maff1->space, maff2->space);
2052         if (equal < 0 || !equal)
2053                 return equal;
2054
2055         for (i = 0; i < maff1->n; ++i) {
2056                 equal = isl_aff_plain_is_equal(maff1->p[i], maff2->p[i]);
2057                 if (equal < 0 || !equal)
2058                         return equal;
2059         }
2060
2061         return 1;
2062 }
2063
2064 __isl_give isl_multi_aff *isl_multi_aff_set_dim_name(
2065         __isl_take isl_multi_aff *maff,
2066         enum isl_dim_type type, unsigned pos, const char *s)
2067 {
2068         int i;
2069
2070         maff = isl_multi_aff_cow(maff);
2071         if (!maff)
2072                 return NULL;
2073
2074         maff->space = isl_space_set_dim_name(maff->space, type, pos, s);
2075         if (!maff->space)
2076                 return isl_multi_aff_free(maff);
2077         for (i = 0; i < maff->n; ++i) {
2078                 maff->p[i] = isl_aff_set_dim_name(maff->p[i], type, pos, s);
2079                 if (!maff->p[i])
2080                         return isl_multi_aff_free(maff);
2081         }
2082
2083         return maff;
2084 }
2085
2086 __isl_give isl_multi_aff *isl_multi_aff_drop_dims(__isl_take isl_multi_aff *maff,
2087         enum isl_dim_type type, unsigned first, unsigned n)
2088 {
2089         int i;
2090
2091         maff = isl_multi_aff_cow(maff);
2092         if (!maff)
2093                 return NULL;
2094
2095         maff->space = isl_space_drop_dims(maff->space, type, first, n);
2096         if (!maff->space)
2097                 return isl_multi_aff_free(maff);
2098         for (i = 0; i < maff->n; ++i) {
2099                 maff->p[i] = isl_aff_drop_dims(maff->p[i], type, first, n);
2100                 if (!maff->p[i])
2101                         return isl_multi_aff_free(maff);
2102         }
2103
2104         return maff;
2105 }
2106
2107 #undef PW
2108 #define PW isl_pw_multi_aff
2109 #undef EL
2110 #define EL isl_multi_aff
2111 #undef EL_IS_ZERO
2112 #define EL_IS_ZERO is_empty
2113 #undef ZERO
2114 #define ZERO empty
2115 #undef IS_ZERO
2116 #define IS_ZERO is_empty
2117 #undef FIELD
2118 #define FIELD maff
2119
2120 #define NO_NEG
2121 #define NO_EVAL
2122 #define NO_OPT
2123 #define NO_INVOLVES_DIMS
2124 #define NO_MOVE_DIMS
2125 #define NO_INSERT_DIMS
2126 #define NO_LIFT
2127 #define NO_MORPH
2128
2129 #include <isl_pw_templ.c>
2130
2131 /* Construct a map mapping the domain the piecewise multi-affine expression
2132  * to its range, with each dimension in the range equated to the
2133  * corresponding affine expression on its cell.
2134  */
2135 __isl_give isl_map *isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
2136 {
2137         int i;
2138         isl_map *map;
2139
2140         if (!pma)
2141                 return NULL;
2142
2143         map = isl_map_empty(isl_pw_multi_aff_get_space(pma));
2144
2145         for (i = 0; i < pma->n; ++i) {
2146                 isl_multi_aff *maff;
2147                 isl_basic_map *bmap;
2148                 isl_map *map_i;
2149
2150                 maff = isl_multi_aff_copy(pma->p[i].maff);
2151                 bmap = isl_basic_map_from_multi_aff(maff);
2152                 map_i = isl_map_from_basic_map(bmap);
2153                 map_i = isl_map_intersect_domain(map_i,
2154                                                 isl_set_copy(pma->p[i].set));
2155                 map = isl_map_union_disjoint(map, map_i);
2156         }
2157
2158         isl_pw_multi_aff_free(pma);
2159         return map;
2160 }
2161
2162 __isl_give isl_set *isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
2163 {
2164         if (!isl_space_is_set(pma->dim))
2165                 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
2166                         "isl_pw_multi_aff cannot be converted into an isl_set",
2167                         return isl_pw_multi_aff_free(pma));
2168
2169         return isl_map_from_pw_multi_aff(pma);
2170 }
2171
2172 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
2173  * This obivously only works if the input "map" is single-valued.
2174  * If so, we compute the lexicographic minimum of the image in the form
2175  * of an isl_pw_multi_aff.  Since the image is unique, it is equal
2176  * to its lexicographic minimum.
2177  * If the input is not single-valued, we produce an error.
2178  */
2179 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_map(__isl_take isl_map *map)
2180 {
2181         int i;
2182         int sv;
2183         isl_pw_multi_aff *pma;
2184
2185         if (!map)
2186                 return NULL;
2187
2188         sv = isl_map_is_single_valued(map);
2189         if (sv < 0)
2190                 goto error;
2191         if (!sv)
2192                 isl_die(isl_map_get_ctx(map), isl_error_invalid,
2193                         "map is not single-valued", goto error);
2194         map = isl_map_make_disjoint(map);
2195         if (!map)
2196                 return NULL;
2197
2198         pma = isl_pw_multi_aff_empty(isl_map_get_space(map));
2199
2200         for (i = 0; i < map->n; ++i) {
2201                 isl_pw_multi_aff *pma_i;
2202                 isl_basic_map *bmap;
2203                 bmap = isl_basic_map_copy(map->p[i]);
2204                 pma_i = isl_basic_map_lexmin_pw_multi_aff(bmap);
2205                 pma = isl_pw_multi_aff_add_disjoint(pma, pma_i);
2206         }
2207
2208         isl_map_free(map);
2209         return pma;
2210 error:
2211         isl_map_free(map);
2212         return NULL;
2213 }
2214
2215 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_set(__isl_take isl_set *set)
2216 {
2217         return isl_pw_multi_aff_from_map(set);
2218 }
2219
2220 /* Plug in "subs" for dimension "type", "pos" of "aff".
2221  *
2222  * Let i be the dimension to replace and let "subs" be of the form
2223  *
2224  *      f/d
2225  *
2226  * and "aff" of the form
2227  *
2228  *      (a i + g)/m
2229  *
2230  * The result is
2231  *
2232  *      floor((a f + d g')/(m d))
2233  *
2234  * where g' is the result of plugging in "subs" in each of the integer
2235  * divisions in g.
2236  */
2237 __isl_give isl_aff *isl_aff_substitute(__isl_take isl_aff *aff,
2238         enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs)
2239 {
2240         isl_ctx *ctx;
2241         isl_int v;
2242
2243         aff = isl_aff_cow(aff);
2244         if (!aff || !subs)
2245                 return isl_aff_free(aff);
2246
2247         ctx = isl_aff_get_ctx(aff);
2248         if (!isl_space_is_equal(aff->ls->dim, subs->ls->dim))
2249                 isl_die(ctx, isl_error_invalid,
2250                         "spaces don't match", return isl_aff_free(aff));
2251         if (isl_local_space_dim(subs->ls, isl_dim_div) != 0)
2252                 isl_die(ctx, isl_error_unsupported,
2253                         "cannot handle divs yet", return isl_aff_free(aff));
2254
2255         aff->ls = isl_local_space_substitute(aff->ls, type, pos, subs);
2256         if (!aff->ls)
2257                 return isl_aff_free(aff);
2258
2259         aff->v = isl_vec_cow(aff->v);
2260         if (!aff->v)
2261                 return isl_aff_free(aff);
2262
2263         pos += isl_local_space_offset(aff->ls, type);
2264
2265         isl_int_init(v);
2266         isl_int_set(v, aff->v->el[1 + pos]);
2267         isl_int_set_si(aff->v->el[1 + pos], 0);
2268         isl_seq_combine(aff->v->el + 1, subs->v->el[0], aff->v->el + 1,
2269                         v, subs->v->el + 1, subs->v->size - 1);
2270         isl_int_mul(aff->v->el[0], aff->v->el[0], subs->v->el[0]);
2271         isl_int_clear(v);
2272
2273         return aff;
2274 }
2275
2276 /* Plug in "subs" for dimension "type", "pos" in each of the affine
2277  * expressions in "maff".
2278  */
2279 __isl_give isl_multi_aff *isl_multi_aff_substitute(
2280         __isl_take isl_multi_aff *maff, enum isl_dim_type type, unsigned pos,
2281         __isl_keep isl_aff *subs)
2282 {
2283         int i;
2284
2285         maff = isl_multi_aff_cow(maff);
2286         if (!maff || !subs)
2287                 return isl_multi_aff_free(maff);
2288
2289         if (type == isl_dim_in)
2290                 type = isl_dim_set;
2291
2292         for (i = 0; i < maff->n; ++i) {
2293                 maff->p[i] = isl_aff_substitute(maff->p[i], type, pos, subs);
2294                 if (!maff->p[i])
2295                         return isl_multi_aff_free(maff);
2296         }
2297
2298         return maff;
2299 }
2300
2301 /* Plug in "subs" for dimension "type", "pos" of "pma".
2302  *
2303  * pma is of the form
2304  *
2305  *      A_i(v) -> M_i(v)
2306  *
2307  * while subs is of the form
2308  *
2309  *      v' = B_j(v) -> S_j
2310  *
2311  * Each pair i,j such that C_ij = A_i \cap B_i is non-empty
2312  * has a contribution in the result, in particular
2313  *
2314  *      C_ij(S_j) -> M_i(S_j)
2315  *
2316  * Note that plugging in S_j in C_ij may also result in an empty set
2317  * and this contribution should simply be discarded.
2318  */
2319 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_substitute(
2320         __isl_take isl_pw_multi_aff *pma, enum isl_dim_type type, unsigned pos,
2321         __isl_keep isl_pw_aff *subs)
2322 {
2323         int i, j, n;
2324         isl_pw_multi_aff *res;
2325
2326         if (!pma || !subs)
2327                 return isl_pw_multi_aff_free(pma);
2328
2329         n = pma->n * subs->n;
2330         res = isl_pw_multi_aff_alloc_size(isl_space_copy(pma->dim), n);
2331
2332         for (i = 0; i < pma->n; ++i) {
2333                 for (j = 0; j < subs->n; ++j) {
2334                         isl_set *common;
2335                         isl_multi_aff *res_ij;
2336                         common = isl_set_intersect(
2337                                         isl_set_copy(pma->p[i].set),
2338                                         isl_set_copy(subs->p[j].set));
2339                         common = isl_set_substitute(common,
2340                                         type, pos, subs->p[j].aff);
2341                         if (isl_set_plain_is_empty(common)) {
2342                                 isl_set_free(common);
2343                                 continue;
2344                         }
2345
2346                         res_ij = isl_multi_aff_substitute(
2347                                         isl_multi_aff_copy(pma->p[i].maff),
2348                                         type, pos, subs->p[j].aff);
2349
2350                         res = isl_pw_multi_aff_add_piece(res, common, res_ij);
2351                 }
2352         }
2353
2354         isl_pw_multi_aff_free(pma);
2355         return res;
2356 }
2357
2358 /* Extend the local space of "dst" to include the divs
2359  * in the local space of "src".
2360  */
2361 __isl_give isl_aff *isl_aff_align_divs(__isl_take isl_aff *dst,
2362         __isl_keep isl_aff *src)
2363 {
2364         isl_ctx *ctx;
2365         int *exp1 = NULL;
2366         int *exp2 = NULL;
2367         isl_mat *div;
2368
2369         if (!src || !dst)
2370                 return isl_aff_free(dst);
2371
2372         ctx = isl_aff_get_ctx(src);
2373         if (!isl_space_is_equal(src->ls->dim, dst->ls->dim))
2374                 isl_die(ctx, isl_error_invalid,
2375                         "spaces don't match", goto error);
2376
2377         if (src->ls->div->n_row == 0)
2378                 return dst;
2379
2380         exp1 = isl_alloc_array(ctx, int, src->ls->div->n_row);
2381         exp2 = isl_alloc_array(ctx, int, dst->ls->div->n_row);
2382         if (!exp1 || !exp2)
2383                 goto error;
2384
2385         div = isl_merge_divs(src->ls->div, dst->ls->div, exp1, exp2);
2386         dst = isl_aff_expand_divs(dst, div, exp2);
2387         free(exp1);
2388         free(exp2);
2389
2390         return dst;
2391 error:
2392         free(exp1);
2393         free(exp2);
2394         return isl_aff_free(dst);
2395 }
2396
2397 /* Adjust the local spaces of the affine expressions in "maff"
2398  * such that they all have the save divs.
2399  */
2400 __isl_give isl_multi_aff *isl_multi_aff_align_divs(
2401         __isl_take isl_multi_aff *maff)
2402 {
2403         int i;
2404
2405         if (!maff)
2406                 return NULL;
2407         if (maff->n == 0)
2408                 return maff;
2409         maff = isl_multi_aff_cow(maff);
2410         if (!maff)
2411                 return NULL;
2412
2413         for (i = 1; i < maff->n; ++i)
2414                 maff->p[0] = isl_aff_align_divs(maff->p[0], maff->p[i]);
2415         for (i = 1; i < maff->n; ++i) {
2416                 maff->p[i] = isl_aff_align_divs(maff->p[i], maff->p[0]);
2417                 if (!maff->p[i])
2418                         return isl_multi_aff_free(maff);
2419         }
2420
2421         return maff;
2422 }
2423
2424 __isl_give isl_aff *isl_aff_lift(__isl_take isl_aff *aff)
2425 {
2426         aff = isl_aff_cow(aff);
2427         if (!aff)
2428                 return NULL;
2429
2430         aff->ls = isl_local_space_lift(aff->ls);
2431         if (!aff->ls)
2432                 return isl_aff_free(aff);
2433
2434         return aff;
2435 }
2436
2437 /* Lift "maff" to a space with extra dimensions such that the result
2438  * has no more existentially quantified variables.
2439  * If "ls" is not NULL, then *ls is assigned the local space that lies
2440  * at the basis of the lifting applied to "maff".
2441  */
2442 __isl_give isl_multi_aff *isl_multi_aff_lift(__isl_take isl_multi_aff *maff,
2443         __isl_give isl_local_space **ls)
2444 {
2445         int i;
2446         isl_space *space;
2447         unsigned n_div;
2448
2449         if (ls)
2450                 *ls = NULL;
2451
2452         if (!maff)
2453                 return NULL;
2454
2455         if (maff->n == 0) {
2456                 if (ls) {
2457                         isl_space *space = isl_multi_aff_get_domain_space(maff);
2458                         *ls = isl_local_space_from_space(space);
2459                         if (!*ls)
2460                                 return isl_multi_aff_free(maff);
2461                 }
2462                 return maff;
2463         }
2464
2465         maff = isl_multi_aff_cow(maff);
2466         maff = isl_multi_aff_align_divs(maff);
2467         if (!maff)
2468                 return NULL;
2469
2470         n_div = isl_aff_dim(maff->p[0], isl_dim_div);
2471         space = isl_multi_aff_get_space(maff);
2472         space = isl_space_lift(isl_space_domain(space), n_div);
2473         space = isl_space_extend_domain_with_range(space,
2474                                                 isl_multi_aff_get_space(maff));
2475         if (!space)
2476                 return isl_multi_aff_free(maff);
2477         isl_space_free(maff->space);
2478         maff->space = space;
2479
2480         if (ls) {
2481                 *ls = isl_aff_get_domain_local_space(maff->p[0]);
2482                 if (!*ls)
2483                         return isl_multi_aff_free(maff);
2484         }
2485
2486         for (i = 0; i < maff->n; ++i) {
2487                 maff->p[i] = isl_aff_lift(maff->p[i]);
2488                 if (!maff->p[i])
2489                         goto error;
2490         }
2491
2492         return maff;
2493 error:
2494         if (ls)
2495                 isl_local_space_free(*ls);
2496         return isl_multi_aff_free(maff);
2497 }