isl_aff.c

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