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_div *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_set_tuple_id(__isl_take isl_pw_aff *pwaff,
1163         __isl_take isl_id *id)
1164 {
1165         isl_space *dim;
1166
1167         dim = isl_pw_aff_get_space(pwaff);
1168         dim = isl_space_set_tuple_id(dim, isl_dim_in, id);
1169
1170         return isl_pw_aff_reset_space(pwaff, dim);
1171 }
1172
1173 __isl_give isl_pw_aff *isl_pw_aff_from_aff(__isl_take isl_aff *aff)
1174 {
1175         isl_set *dom = isl_set_universe(isl_aff_get_domain_space(aff));
1176         return isl_pw_aff_alloc(dom, aff);
1177 }
1178
1179 #undef PW
1180 #define PW isl_pw_aff
1181 #undef EL
1182 #define EL isl_aff
1183 #undef EL_IS_ZERO
1184 #define EL_IS_ZERO is_empty
1185 #undef ZERO
1186 #define ZERO empty
1187 #undef IS_ZERO
1188 #define IS_ZERO is_empty
1189 #undef FIELD
1190 #define FIELD aff
1191
1192 #define NO_EVAL
1193 #define NO_OPT
1194 #define NO_MOVE_DIMS
1195 #define NO_LIFT
1196 #define NO_MORPH
1197
1198 #include <isl_pw_templ.c>
1199
1200 static __isl_give isl_set *align_params_pw_pw_set_and(
1201         __isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2,
1202         __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1203                                     __isl_take isl_pw_aff *pwaff2))
1204 {
1205         if (!pwaff1 || !pwaff2)
1206                 goto error;
1207         if (isl_space_match(pwaff1->dim, isl_dim_param,
1208                           pwaff2->dim, isl_dim_param))
1209                 return fn(pwaff1, pwaff2);
1210         if (!isl_space_has_named_params(pwaff1->dim) ||
1211             !isl_space_has_named_params(pwaff2->dim))
1212                 isl_die(isl_pw_aff_get_ctx(pwaff1), isl_error_invalid,
1213                         "unaligned unnamed parameters", goto error);
1214         pwaff1 = isl_pw_aff_align_params(pwaff1, isl_pw_aff_get_space(pwaff2));
1215         pwaff2 = isl_pw_aff_align_params(pwaff2, isl_pw_aff_get_space(pwaff1));
1216         return fn(pwaff1, pwaff2);
1217 error:
1218         isl_pw_aff_free(pwaff1);
1219         isl_pw_aff_free(pwaff2);
1220         return NULL;
1221 }
1222
1223 /* Compute a piecewise quasi-affine expression with a domain that
1224  * is the union of those of pwaff1 and pwaff2 and such that on each
1225  * cell, the quasi-affine expression is the better (according to cmp)
1226  * of those of pwaff1 and pwaff2.  If only one of pwaff1 or pwaff2
1227  * is defined on a given cell, then the associated expression
1228  * is the defined one.
1229  */
1230 static __isl_give isl_pw_aff *pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1231         __isl_take isl_pw_aff *pwaff2,
1232         __isl_give isl_basic_set *(*cmp)(__isl_take isl_aff *aff1,
1233                                         __isl_take isl_aff *aff2))
1234 {
1235         int i, j, n;
1236         isl_pw_aff *res;
1237         isl_ctx *ctx;
1238         isl_set *set;
1239
1240         if (!pwaff1 || !pwaff2)
1241                 goto error;
1242
1243         ctx = isl_space_get_ctx(pwaff1->dim);
1244         if (!isl_space_is_equal(pwaff1->dim, pwaff2->dim))
1245                 isl_die(ctx, isl_error_invalid,
1246                         "arguments should live in same space", goto error);
1247
1248         if (isl_pw_aff_is_empty(pwaff1)) {
1249                 isl_pw_aff_free(pwaff1);
1250                 return pwaff2;
1251         }
1252
1253         if (isl_pw_aff_is_empty(pwaff2)) {
1254                 isl_pw_aff_free(pwaff2);
1255                 return pwaff1;
1256         }
1257
1258         n = 2 * (pwaff1->n + 1) * (pwaff2->n + 1);
1259         res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n);
1260
1261         for (i = 0; i < pwaff1->n; ++i) {
1262                 set = isl_set_copy(pwaff1->p[i].set);
1263                 for (j = 0; j < pwaff2->n; ++j) {
1264                         struct isl_set *common;
1265                         isl_set *better;
1266
1267                         common = isl_set_intersect(
1268                                         isl_set_copy(pwaff1->p[i].set),
1269                                         isl_set_copy(pwaff2->p[j].set));
1270                         better = isl_set_from_basic_set(cmp(
1271                                         isl_aff_copy(pwaff2->p[j].aff),
1272                                         isl_aff_copy(pwaff1->p[i].aff)));
1273                         better = isl_set_intersect(common, better);
1274                         if (isl_set_plain_is_empty(better)) {
1275                                 isl_set_free(better);
1276                                 continue;
1277                         }
1278                         set = isl_set_subtract(set, isl_set_copy(better));
1279
1280                         res = isl_pw_aff_add_piece(res, better,
1281                                                 isl_aff_copy(pwaff2->p[j].aff));
1282                 }
1283                 res = isl_pw_aff_add_piece(res, set,
1284                                                 isl_aff_copy(pwaff1->p[i].aff));
1285         }
1286
1287         for (j = 0; j < pwaff2->n; ++j) {
1288                 set = isl_set_copy(pwaff2->p[j].set);
1289                 for (i = 0; i < pwaff1->n; ++i)
1290                         set = isl_set_subtract(set,
1291                                         isl_set_copy(pwaff1->p[i].set));
1292                 res = isl_pw_aff_add_piece(res, set,
1293                                                 isl_aff_copy(pwaff2->p[j].aff));
1294         }
1295
1296         isl_pw_aff_free(pwaff1);
1297         isl_pw_aff_free(pwaff2);
1298
1299         return res;
1300 error:
1301         isl_pw_aff_free(pwaff1);
1302         isl_pw_aff_free(pwaff2);
1303         return NULL;
1304 }
1305
1306 /* Compute a piecewise quasi-affine expression with a domain that
1307  * is the union of those of pwaff1 and pwaff2 and such that on each
1308  * cell, the quasi-affine expression is the maximum of those of pwaff1
1309  * and pwaff2.  If only one of pwaff1 or pwaff2 is defined on a given
1310  * cell, then the associated expression is the defined one.
1311  */
1312 static __isl_give isl_pw_aff *pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1313         __isl_take isl_pw_aff *pwaff2)
1314 {
1315         return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_ge_basic_set);
1316 }
1317
1318 __isl_give isl_pw_aff *isl_pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1319         __isl_take isl_pw_aff *pwaff2)
1320 {
1321         return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_union_max);
1322 }
1323
1324 /* Compute a piecewise quasi-affine expression with a domain that
1325  * is the union of those of pwaff1 and pwaff2 and such that on each
1326  * cell, the quasi-affine expression is the minimum of those of pwaff1
1327  * and pwaff2.  If only one of pwaff1 or pwaff2 is defined on a given
1328  * cell, then the associated expression is the defined one.
1329  */
1330 static __isl_give isl_pw_aff *pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1331         __isl_take isl_pw_aff *pwaff2)
1332 {
1333         return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_le_basic_set);
1334 }
1335
1336 __isl_give isl_pw_aff *isl_pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1337         __isl_take isl_pw_aff *pwaff2)
1338 {
1339         return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_union_min);
1340 }
1341
1342 __isl_give isl_pw_aff *isl_pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1343         __isl_take isl_pw_aff *pwaff2, int max)
1344 {
1345         if (max)
1346                 return isl_pw_aff_union_max(pwaff1, pwaff2);
1347         else
1348                 return isl_pw_aff_union_min(pwaff1, pwaff2);
1349 }
1350
1351 /* Construct a map with as domain the domain of pwaff and
1352  * one-dimensional range corresponding to the affine expressions.
1353  */
1354 static __isl_give isl_map *map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1355 {
1356         int i;
1357         isl_space *dim;
1358         isl_map *map;
1359
1360         if (!pwaff)
1361                 return NULL;
1362
1363         dim = isl_pw_aff_get_space(pwaff);
1364         map = isl_map_empty(dim);
1365
1366         for (i = 0; i < pwaff->n; ++i) {
1367                 isl_basic_map *bmap;
1368                 isl_map *map_i;
1369
1370                 bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
1371                 map_i = isl_map_from_basic_map(bmap);
1372                 map_i = isl_map_intersect_domain(map_i,
1373                                                 isl_set_copy(pwaff->p[i].set));
1374                 map = isl_map_union_disjoint(map, map_i);
1375         }
1376
1377         isl_pw_aff_free(pwaff);
1378
1379         return map;
1380 }
1381
1382 /* Construct a map with as domain the domain of pwaff and
1383  * one-dimensional range corresponding to the affine expressions.
1384  */
1385 __isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1386 {
1387         if (isl_space_is_set(pwaff->dim))
1388                 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1389                         "space of input is not a map",
1390                         return isl_pw_aff_free(pwaff));
1391         return map_from_pw_aff(pwaff);
1392 }
1393
1394 /* Construct a one-dimensional set with as parameter domain
1395  * the domain of pwaff and the single set dimension
1396  * corresponding to the affine expressions.
1397  */
1398 __isl_give isl_set *isl_set_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1399 {
1400         if (!isl_space_is_set(pwaff->dim))
1401                 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1402                         "space of input is not a set",
1403                         return isl_pw_aff_free(pwaff));
1404         return map_from_pw_aff(pwaff);
1405 }
1406
1407 /* Return a set containing those elements in the domain
1408  * of pwaff where it is non-negative.
1409  */
1410 __isl_give isl_set *isl_pw_aff_nonneg_set(__isl_take isl_pw_aff *pwaff)
1411 {
1412         int i;
1413         isl_set *set;
1414
1415         if (!pwaff)
1416                 return NULL;
1417
1418         set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1419
1420         for (i = 0; i < pwaff->n; ++i) {
1421                 isl_basic_set *bset;
1422                 isl_set *set_i;
1423
1424                 bset = isl_aff_nonneg_basic_set(isl_aff_copy(pwaff->p[i].aff));
1425                 set_i = isl_set_from_basic_set(bset);
1426                 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1427                 set = isl_set_union_disjoint(set, set_i);
1428         }
1429
1430         isl_pw_aff_free(pwaff);
1431
1432         return set;
1433 }
1434
1435 /* Return a set containing those elements in the domain
1436  * of pwaff where it is zero.
1437  */
1438 __isl_give isl_set *isl_pw_aff_zero_set(__isl_take isl_pw_aff *pwaff)
1439 {
1440         int i;
1441         isl_set *set;
1442
1443         if (!pwaff)
1444                 return NULL;
1445
1446         set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1447
1448         for (i = 0; i < pwaff->n; ++i) {
1449                 isl_basic_set *bset;
1450                 isl_set *set_i;
1451
1452                 bset = isl_aff_zero_basic_set(isl_aff_copy(pwaff->p[i].aff));
1453                 set_i = isl_set_from_basic_set(bset);
1454                 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1455                 set = isl_set_union_disjoint(set, set_i);
1456         }
1457
1458         isl_pw_aff_free(pwaff);
1459
1460         return set;
1461 }
1462
1463 /* Return a set containing those elements in the domain
1464  * of pwaff where it is not zero.
1465  */
1466 __isl_give isl_set *isl_pw_aff_non_zero_set(__isl_take isl_pw_aff *pwaff)
1467 {
1468         return isl_set_complement(isl_pw_aff_zero_set(pwaff));
1469 }
1470
1471 /* Return a set containing those elements in the shared domain
1472  * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
1473  *
1474  * We compute the difference on the shared domain and then construct
1475  * the set of values where this difference is non-negative.
1476  * If strict is set, we first subtract 1 from the difference.
1477  * If equal is set, we only return the elements where pwaff1 and pwaff2
1478  * are equal.
1479  */
1480 static __isl_give isl_set *pw_aff_gte_set(__isl_take isl_pw_aff *pwaff1,
1481         __isl_take isl_pw_aff *pwaff2, int strict, int equal)
1482 {
1483         isl_set *set1, *set2;
1484
1485         set1 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff1));
1486         set2 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff2));
1487         set1 = isl_set_intersect(set1, set2);
1488         pwaff1 = isl_pw_aff_intersect_domain(pwaff1, isl_set_copy(set1));
1489         pwaff2 = isl_pw_aff_intersect_domain(pwaff2, isl_set_copy(set1));
1490         pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_neg(pwaff2));
1491
1492         if (strict) {
1493                 isl_space *dim = isl_set_get_space(set1);
1494                 isl_aff *aff;
1495                 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
1496                 aff = isl_aff_add_constant_si(aff, -1);
1497                 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_alloc(set1, aff));
1498         } else
1499                 isl_set_free(set1);
1500
1501         if (equal)
1502                 return isl_pw_aff_zero_set(pwaff1);
1503         return isl_pw_aff_nonneg_set(pwaff1);
1504 }
1505
1506 /* Return a set containing those elements in the shared domain
1507  * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
1508  */
1509 static __isl_give isl_set *pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1510         __isl_take isl_pw_aff *pwaff2)
1511 {
1512         return pw_aff_gte_set(pwaff1, pwaff2, 0, 1);
1513 }
1514
1515 __isl_give isl_set *isl_pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1516         __isl_take isl_pw_aff *pwaff2)
1517 {
1518         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_eq_set);
1519 }
1520
1521 /* Return a set containing those elements in the shared domain
1522  * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
1523  */
1524 static __isl_give isl_set *pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1525         __isl_take isl_pw_aff *pwaff2)
1526 {
1527         return pw_aff_gte_set(pwaff1, pwaff2, 0, 0);
1528 }
1529
1530 __isl_give isl_set *isl_pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1531         __isl_take isl_pw_aff *pwaff2)
1532 {
1533         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ge_set);
1534 }
1535
1536 /* Return a set containing those elements in the shared domain
1537  * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
1538  */
1539 static __isl_give isl_set *pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1540         __isl_take isl_pw_aff *pwaff2)
1541 {
1542         return pw_aff_gte_set(pwaff1, pwaff2, 1, 0);
1543 }
1544
1545 __isl_give isl_set *isl_pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1546         __isl_take isl_pw_aff *pwaff2)
1547 {
1548         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_gt_set);
1549 }
1550
1551 __isl_give isl_set *isl_pw_aff_le_set(__isl_take isl_pw_aff *pwaff1,
1552         __isl_take isl_pw_aff *pwaff2)
1553 {
1554         return isl_pw_aff_ge_set(pwaff2, pwaff1);
1555 }
1556
1557 __isl_give isl_set *isl_pw_aff_lt_set(__isl_take isl_pw_aff *pwaff1,
1558         __isl_take isl_pw_aff *pwaff2)
1559 {
1560         return isl_pw_aff_gt_set(pwaff2, pwaff1);
1561 }
1562
1563 /* Return a set containing those elements in the shared domain
1564  * of the elements of list1 and list2 where each element in list1
1565  * has the relation specified by "fn" with each element in list2.
1566  */
1567 static __isl_give isl_set *pw_aff_list_set(__isl_take isl_pw_aff_list *list1,
1568         __isl_take isl_pw_aff_list *list2,
1569         __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1570                                     __isl_take isl_pw_aff *pwaff2))
1571 {
1572         int i, j;
1573         isl_ctx *ctx;
1574         isl_set *set;
1575
1576         if (!list1 || !list2)
1577                 goto error;
1578
1579         ctx = isl_pw_aff_list_get_ctx(list1);
1580         if (list1->n < 1 || list2->n < 1)
1581                 isl_die(ctx, isl_error_invalid,
1582                         "list should contain at least one element", goto error);
1583
1584         set = isl_set_universe(isl_pw_aff_get_domain_space(list1->p[0]));
1585         for (i = 0; i < list1->n; ++i)
1586                 for (j = 0; j < list2->n; ++j) {
1587                         isl_set *set_ij;
1588
1589                         set_ij = fn(isl_pw_aff_copy(list1->p[i]),
1590                                     isl_pw_aff_copy(list2->p[j]));
1591                         set = isl_set_intersect(set, set_ij);
1592                 }
1593
1594         isl_pw_aff_list_free(list1);
1595         isl_pw_aff_list_free(list2);
1596         return set;
1597 error:
1598         isl_pw_aff_list_free(list1);
1599         isl_pw_aff_list_free(list2);
1600         return NULL;
1601 }
1602
1603 /* Return a set containing those elements in the shared domain
1604  * of the elements of list1 and list2 where each element in list1
1605  * is equal to each element in list2.
1606  */
1607 __isl_give isl_set *isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list *list1,
1608         __isl_take isl_pw_aff_list *list2)
1609 {
1610         return pw_aff_list_set(list1, list2, &isl_pw_aff_eq_set);
1611 }
1612
1613 __isl_give isl_set *isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list *list1,
1614         __isl_take isl_pw_aff_list *list2)
1615 {
1616         return pw_aff_list_set(list1, list2, &isl_pw_aff_ne_set);
1617 }
1618
1619 /* Return a set containing those elements in the shared domain
1620  * of the elements of list1 and list2 where each element in list1
1621  * is less than or equal to each element in list2.
1622  */
1623 __isl_give isl_set *isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list *list1,
1624         __isl_take isl_pw_aff_list *list2)
1625 {
1626         return pw_aff_list_set(list1, list2, &isl_pw_aff_le_set);
1627 }
1628
1629 __isl_give isl_set *isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list *list1,
1630         __isl_take isl_pw_aff_list *list2)
1631 {
1632         return pw_aff_list_set(list1, list2, &isl_pw_aff_lt_set);
1633 }
1634
1635 __isl_give isl_set *isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list *list1,
1636         __isl_take isl_pw_aff_list *list2)
1637 {
1638         return pw_aff_list_set(list1, list2, &isl_pw_aff_ge_set);
1639 }
1640
1641 __isl_give isl_set *isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list *list1,
1642         __isl_take isl_pw_aff_list *list2)
1643 {
1644         return pw_aff_list_set(list1, list2, &isl_pw_aff_gt_set);
1645 }
1646
1647
1648 /* Return a set containing those elements in the shared domain
1649  * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
1650  */
1651 static __isl_give isl_set *pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1652         __isl_take isl_pw_aff *pwaff2)
1653 {
1654         isl_set *set_lt, *set_gt;
1655
1656         set_lt = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1),
1657                                    isl_pw_aff_copy(pwaff2));
1658         set_gt = isl_pw_aff_gt_set(pwaff1, pwaff2);
1659         return isl_set_union_disjoint(set_lt, set_gt);
1660 }
1661
1662 __isl_give isl_set *isl_pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1663         __isl_take isl_pw_aff *pwaff2)
1664 {
1665         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ne_set);
1666 }
1667
1668 __isl_give isl_pw_aff *isl_pw_aff_scale_down(__isl_take isl_pw_aff *pwaff,
1669         isl_int v)
1670 {
1671         int i;
1672
1673         if (isl_int_is_one(v))
1674                 return pwaff;
1675         if (!isl_int_is_pos(v))
1676                 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1677                         "factor needs to be positive",
1678                         return isl_pw_aff_free(pwaff));
1679         pwaff = isl_pw_aff_cow(pwaff);
1680         if (!pwaff)
1681                 return NULL;
1682         if (pwaff->n == 0)
1683                 return pwaff;
1684
1685         for (i = 0; i < pwaff->n; ++i) {
1686                 pwaff->p[i].aff = isl_aff_scale_down(pwaff->p[i].aff, v);
1687                 if (!pwaff->p[i].aff)
1688                         return isl_pw_aff_free(pwaff);
1689         }
1690
1691         return pwaff;
1692 }
1693
1694 __isl_give isl_pw_aff *isl_pw_aff_floor(__isl_take isl_pw_aff *pwaff)
1695 {
1696         int i;
1697
1698         pwaff = isl_pw_aff_cow(pwaff);
1699         if (!pwaff)
1700                 return NULL;
1701         if (pwaff->n == 0)
1702                 return pwaff;
1703
1704         for (i = 0; i < pwaff->n; ++i) {
1705                 pwaff->p[i].aff = isl_aff_floor(pwaff->p[i].aff);
1706                 if (!pwaff->p[i].aff)
1707                         return isl_pw_aff_free(pwaff);
1708         }
1709
1710         return pwaff;
1711 }
1712
1713 __isl_give isl_pw_aff *isl_pw_aff_ceil(__isl_take isl_pw_aff *pwaff)
1714 {
1715         int i;
1716
1717         pwaff = isl_pw_aff_cow(pwaff);
1718         if (!pwaff)
1719                 return NULL;
1720         if (pwaff->n == 0)
1721                 return pwaff;
1722
1723         for (i = 0; i < pwaff->n; ++i) {
1724                 pwaff->p[i].aff = isl_aff_ceil(pwaff->p[i].aff);
1725                 if (!pwaff->p[i].aff)
1726                         return isl_pw_aff_free(pwaff);
1727         }
1728
1729         return pwaff;
1730 }
1731
1732 /* Return an affine expression that is equal to pwaff_true for elements
1733  * in "cond" and to pwaff_false for elements not in "cond".
1734  * That is, return cond ? pwaff_true : pwaff_false;
1735  */
1736 __isl_give isl_pw_aff *isl_pw_aff_cond(__isl_take isl_set *cond,
1737         __isl_take isl_pw_aff *pwaff_true, __isl_take isl_pw_aff *pwaff_false)
1738 {
1739         isl_set *comp;
1740
1741         comp = isl_set_complement(isl_set_copy(cond));
1742         pwaff_true = isl_pw_aff_intersect_domain(pwaff_true, cond);
1743         pwaff_false = isl_pw_aff_intersect_domain(pwaff_false, comp);
1744
1745         return isl_pw_aff_add_disjoint(pwaff_true, pwaff_false);
1746 }
1747
1748 int isl_aff_is_cst(__isl_keep isl_aff *aff)
1749 {
1750         if (!aff)
1751                 return -1;
1752
1753         return isl_seq_first_non_zero(aff->v->el + 2, aff->v->size - 2) == -1;
1754 }
1755
1756 /* Check whether pwaff is a piecewise constant.
1757  */
1758 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff)
1759 {
1760         int i;
1761
1762         if (!pwaff)
1763                 return -1;
1764
1765         for (i = 0; i < pwaff->n; ++i) {
1766                 int is_cst = isl_aff_is_cst(pwaff->p[i].aff);
1767                 if (is_cst < 0 || !is_cst)
1768                         return is_cst;
1769         }
1770
1771         return 1;
1772 }
1773
1774 __isl_give isl_aff *isl_aff_mul(__isl_take isl_aff *aff1,
1775         __isl_take isl_aff *aff2)
1776 {
1777         if (!isl_aff_is_cst(aff2) && isl_aff_is_cst(aff1))
1778                 return isl_aff_mul(aff2, aff1);
1779
1780         if (!isl_aff_is_cst(aff2))
1781                 isl_die(isl_aff_get_ctx(aff1), isl_error_invalid,
1782                         "at least one affine expression should be constant",
1783                         goto error);
1784
1785         aff1 = isl_aff_cow(aff1);
1786         if (!aff1 || !aff2)
1787                 goto error;
1788
1789         aff1 = isl_aff_scale(aff1, aff2->v->el[1]);
1790         aff1 = isl_aff_scale_down(aff1, aff2->v->el[0]);
1791
1792         isl_aff_free(aff2);
1793         return aff1;
1794 error:
1795         isl_aff_free(aff1);
1796         isl_aff_free(aff2);
1797         return NULL;
1798 }
1799
1800 static __isl_give isl_pw_aff *pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
1801         __isl_take isl_pw_aff *pwaff2)
1802 {
1803         int i, j, n;
1804         isl_pw_aff *res;
1805
1806         if (!pwaff1 || !pwaff2)
1807                 goto error;
1808
1809         n = pwaff1->n * pwaff2->n;
1810         res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n);
1811
1812         for (i = 0; i < pwaff1->n; ++i) {
1813                 for (j = 0; j < pwaff2->n; ++j) {
1814                         isl_set *common;
1815                         isl_aff *prod;
1816                         common = isl_set_intersect(
1817                                         isl_set_copy(pwaff1->p[i].set),
1818                                         isl_set_copy(pwaff2->p[j].set));
1819                         if (isl_set_plain_is_empty(common)) {
1820                                 isl_set_free(common);
1821                                 continue;
1822                         }
1823
1824                         prod = isl_aff_mul(isl_aff_copy(pwaff1->p[i].aff),
1825                                             isl_aff_copy(pwaff2->p[j].aff));
1826
1827                         res = isl_pw_aff_add_piece(res, common, prod);
1828                 }
1829         }
1830
1831         isl_pw_aff_free(pwaff1);
1832         isl_pw_aff_free(pwaff2);
1833         return res;
1834 error:
1835         isl_pw_aff_free(pwaff1);
1836         isl_pw_aff_free(pwaff2);
1837         return NULL;
1838 }
1839
1840 __isl_give isl_pw_aff *isl_pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
1841         __isl_take isl_pw_aff *pwaff2)
1842 {
1843         return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_mul);
1844 }
1845
1846 static __isl_give isl_pw_aff *pw_aff_min(__isl_take isl_pw_aff *pwaff1,
1847         __isl_take isl_pw_aff *pwaff2)
1848 {
1849         isl_set *le;
1850
1851         le = isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1),
1852                                 isl_pw_aff_copy(pwaff2));
1853         return isl_pw_aff_cond(le, pwaff1, pwaff2);
1854 }
1855
1856 __isl_give isl_pw_aff *isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1,
1857         __isl_take isl_pw_aff *pwaff2)
1858 {
1859         return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_min);
1860 }
1861
1862 static __isl_give isl_pw_aff *pw_aff_max(__isl_take isl_pw_aff *pwaff1,
1863         __isl_take isl_pw_aff *pwaff2)
1864 {
1865         isl_set *le;
1866
1867         le = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1),
1868                                 isl_pw_aff_copy(pwaff2));
1869         return isl_pw_aff_cond(le, pwaff1, pwaff2);
1870 }
1871
1872 __isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1,
1873         __isl_take isl_pw_aff *pwaff2)
1874 {
1875         return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_max);
1876 }
1877
1878 static __isl_give isl_pw_aff *pw_aff_list_reduce(
1879         __isl_take isl_pw_aff_list *list,
1880         __isl_give isl_pw_aff *(*fn)(__isl_take isl_pw_aff *pwaff1,
1881                                         __isl_take isl_pw_aff *pwaff2))
1882 {
1883         int i;
1884         isl_ctx *ctx;
1885         isl_pw_aff *res;
1886
1887         if (!list)
1888                 return NULL;
1889
1890         ctx = isl_pw_aff_list_get_ctx(list);
1891         if (list->n < 1)
1892                 isl_die(ctx, isl_error_invalid,
1893                         "list should contain at least one element",
1894                         return isl_pw_aff_list_free(list));
1895
1896         res = isl_pw_aff_copy(list->p[0]);
1897         for (i = 1; i < list->n; ++i)
1898                 res = fn(res, isl_pw_aff_copy(list->p[i]));
1899
1900         isl_pw_aff_list_free(list);
1901         return res;
1902 }
1903
1904 /* Return an isl_pw_aff that maps each element in the intersection of the
1905  * domains of the elements of list to the minimal corresponding affine
1906  * expression.
1907  */
1908 __isl_give isl_pw_aff *isl_pw_aff_list_min(__isl_take isl_pw_aff_list *list)
1909 {
1910         return pw_aff_list_reduce(list, &isl_pw_aff_min);
1911 }
1912
1913 /* Return an isl_pw_aff that maps each element in the intersection of the
1914  * domains of the elements of list to the maximal corresponding affine
1915  * expression.
1916  */
1917 __isl_give isl_pw_aff *isl_pw_aff_list_max(__isl_take isl_pw_aff_list *list)
1918 {
1919         return pw_aff_list_reduce(list, &isl_pw_aff_max);
1920 }