isl_aff.c

   1 /*
   2  * Copyright 2011      INRIA Saclay
   3  * Copyright 2011      Sven Verdoolaege
   4  * Copyright 2012      Ecole Normale Superieure
   5  *
   6  * Use of this software is governed by the GNU LGPLv2.1 license
   7  *
   8  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   9  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
  10  * 91893 Orsay, France
  11  * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
  12  */
  13
  14 #include <isl_ctx_private.h>
  15 #define ISL_DIM_H
  16 #include <isl_map_private.h>
  17 #include <isl_union_map_private.h>
  18 #include <isl_aff_private.h>
  19 #include <isl_space_private.h>
  20 #include <isl_local_space_private.h>
  21 #include <isl_mat_private.h>
  22 #include <isl_list_private.h>
  23 #include <isl/constraint.h>
  24 #include <isl/seq.h>
  25 #include <isl/set.h>
  26 #include <isl_config.h>
  27
  28 __isl_give isl_aff *isl_aff_alloc_vec(__isl_take isl_local_space *ls,
  29         __isl_take isl_vec *v)
  30 {
  31         isl_aff *aff;
  32
  33         if (!ls || !v)
  34                 goto error;
  35
  36         aff = isl_calloc_type(v->ctx, struct isl_aff);
  37         if (!aff)
  38                 goto error;
  39
  40         aff->ref = 1;
  41         aff->ls = ls;
  42         aff->v = v;
  43
  44         return aff;
  45 error:
  46         isl_local_space_free(ls);
  47         isl_vec_free(v);
  48         return NULL;
  49 }
  50
  51 __isl_give isl_aff *isl_aff_alloc(__isl_take isl_local_space *ls)
  52 {
  53         isl_ctx *ctx;
  54         isl_vec *v;
  55         unsigned total;
  56
  57         if (!ls)
  58                 return NULL;
  59
  60         ctx = isl_local_space_get_ctx(ls);
  61         if (!isl_local_space_divs_known(ls))
  62                 isl_die(ctx, isl_error_invalid, "local space has unknown divs",
  63                         goto error);
  64         if (!isl_local_space_is_set(ls))
  65                 isl_die(ctx, isl_error_invalid,
  66                         "domain of affine expression should be a set",
  67                         goto error);
  68
  69         total = isl_local_space_dim(ls, isl_dim_all);
  70         v = isl_vec_alloc(ctx, 1 + 1 + total);
  71         return isl_aff_alloc_vec(ls, v);
  72 error:
  73         isl_local_space_free(ls);
  74         return NULL;
  75 }
  76
  77 __isl_give isl_aff *isl_aff_zero_on_domain(__isl_take isl_local_space *ls)
  78 {
  79         isl_aff *aff;
  80
  81         aff = isl_aff_alloc(ls);
  82         if (!aff)
  83                 return NULL;
  84
  85         isl_int_set_si(aff->v->el[0], 1);
  86         isl_seq_clr(aff->v->el + 1, aff->v->size - 1);
  87
  88         return aff;
  89 }
  90
  91 __isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff)
  92 {
  93         if (!aff)
  94                 return NULL;
  95
  96         aff->ref++;
  97         return aff;
  98 }
  99
 100 __isl_give isl_aff *isl_aff_dup(__isl_keep isl_aff *aff)
 101 {
 102         if (!aff)
 103                 return NULL;
 104
 105         return isl_aff_alloc_vec(isl_local_space_copy(aff->ls),
 106                                  isl_vec_copy(aff->v));
 107 }
 108
 109 __isl_give isl_aff *isl_aff_cow(__isl_take isl_aff *aff)
 110 {
 111         if (!aff)
 112                 return NULL;
 113
 114         if (aff->ref == 1)
 115                 return aff;
 116         aff->ref--;
 117         return isl_aff_dup(aff);
 118 }
 119
 120 void *isl_aff_free(__isl_take isl_aff *aff)
 121 {
 122         if (!aff)
 123                 return NULL;
 124
 125         if (--aff->ref > 0)
 126                 return NULL;
 127
 128         isl_local_space_free(aff->ls);
 129         isl_vec_free(aff->v);
 130
 131         free(aff);
 132
 133         return NULL;
 134 }
 135
 136 isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff)
 137 {
 138         return aff ? isl_local_space_get_ctx(aff->ls) : NULL;
 139 }
 140
 141 /* Externally, an isl_aff has a map space, but internally, the
 142  * ls field corresponds to the domain of that space.
 143  */
 144 int isl_aff_dim(__isl_keep isl_aff *aff, enum isl_dim_type type)
 145 {
 146         if (!aff)
 147                 return 0;
 148         if (type == isl_dim_out)
 149                 return 1;
 150         if (type == isl_dim_in)
 151                 type = isl_dim_set;
 152         return isl_local_space_dim(aff->ls, type);
 153 }
 154
 155 __isl_give isl_space *isl_aff_get_domain_space(__isl_keep isl_aff *aff)
 156 {
 157         return aff ? isl_local_space_get_space(aff->ls) : NULL;
 158 }
 159
 160 __isl_give isl_space *isl_aff_get_space(__isl_keep isl_aff *aff)
 161 {
 162         isl_space *space;
 163         if (!aff)
 164                 return NULL;
 165         space = isl_local_space_get_space(aff->ls);
 166         space = isl_space_from_domain(space);
 167         space = isl_space_add_dims(space, isl_dim_out, 1);
 168         return space;
 169 }
 170
 171 __isl_give isl_local_space *isl_aff_get_domain_local_space(
 172         __isl_keep isl_aff *aff)
 173 {
 174         return aff ? isl_local_space_copy(aff->ls) : NULL;
 175 }
 176
 177 __isl_give isl_local_space *isl_aff_get_local_space(__isl_keep isl_aff *aff)
 178 {
 179         isl_local_space *ls;
 180         if (!aff)
 181                 return NULL;
 182         ls = isl_local_space_copy(aff->ls);
 183         ls = isl_local_space_from_domain(ls);
 184         ls = isl_local_space_add_dims(ls, isl_dim_out, 1);
 185         return ls;
 186 }
 187
 188 /* Externally, an isl_aff has a map space, but internally, the
 189  * ls field corresponds to the domain of that space.
 190  */
 191 const char *isl_aff_get_dim_name(__isl_keep isl_aff *aff,
 192         enum isl_dim_type type, unsigned pos)
 193 {
 194         if (!aff)
 195                 return NULL;
 196         if (type == isl_dim_out)
 197                 return NULL;
 198         if (type == isl_dim_in)
 199                 type = isl_dim_set;
 200         return isl_local_space_get_dim_name(aff->ls, type, pos);
 201 }
 202
 203 __isl_give isl_aff *isl_aff_reset_domain_space(__isl_take isl_aff *aff,
 204         __isl_take isl_space *dim)
 205 {
 206         aff = isl_aff_cow(aff);
 207         if (!aff || !dim)
 208                 goto error;
 209
 210         aff->ls = isl_local_space_reset_space(aff->ls, dim);
 211         if (!aff->ls)
 212                 return isl_aff_free(aff);
 213
 214         return aff;
 215 error:
 216         isl_aff_free(aff);
 217         isl_space_free(dim);
 218         return NULL;
 219 }
 220
 221 /* Reset the space of "aff".  This function is called from isl_pw_templ.c
 222  * and doesn't know if the space of an element object is represented
 223  * directly or through its domain.  It therefore passes along both.
 224  */
 225 __isl_give isl_aff *isl_aff_reset_space_and_domain(__isl_take isl_aff *aff,
 226         __isl_take isl_space *space, __isl_take isl_space *domain)
 227 {
 228         isl_space_free(space);
 229         return isl_aff_reset_domain_space(aff, domain);
 230 }
 231
 232 /* Reorder the coefficients of the affine expression based
 233  * on the given reodering.
 234  * The reordering r is assumed to have been extended with the local
 235  * variables.
 236  */
 237 static __isl_give isl_vec *vec_reorder(__isl_take isl_vec *vec,
 238         __isl_take isl_reordering *r, int n_div)
 239 {
 240         isl_vec *res;
 241         int i;
 242
 243         if (!vec || !r)
 244                 goto error;
 245
 246         res = isl_vec_alloc(vec->ctx,
 247                             2 + isl_space_dim(r->dim, isl_dim_all) + n_div);
 248         isl_seq_cpy(res->el, vec->el, 2);
 249         isl_seq_clr(res->el + 2, res->size - 2);
 250         for (i = 0; i < r->len; ++i)
 251                 isl_int_set(res->el[2 + r->pos[i]], vec->el[2 + i]);
 252
 253         isl_reordering_free(r);
 254         isl_vec_free(vec);
 255         return res;
 256 error:
 257         isl_vec_free(vec);
 258         isl_reordering_free(r);
 259         return NULL;
 260 }
 261
 262 /* Reorder the dimensions of the domain of "aff" according
 263  * to the given reordering.
 264  */
 265 __isl_give isl_aff *isl_aff_realign_domain(__isl_take isl_aff *aff,
 266         __isl_take isl_reordering *r)
 267 {
 268         aff = isl_aff_cow(aff);
 269         if (!aff)
 270                 goto error;
 271
 272         r = isl_reordering_extend(r, aff->ls->div->n_row);
 273         aff->v = vec_reorder(aff->v, isl_reordering_copy(r),
 274                                 aff->ls->div->n_row);
 275         aff->ls = isl_local_space_realign(aff->ls, r);
 276
 277         if (!aff->v || !aff->ls)
 278                 return isl_aff_free(aff);
 279
 280         return aff;
 281 error:
 282         isl_aff_free(aff);
 283         isl_reordering_free(r);
 284         return NULL;
 285 }
 286
 287 __isl_give isl_aff *isl_aff_align_params(__isl_take isl_aff *aff,
 288         __isl_take isl_space *model)
 289 {
 290         if (!aff || !model)
 291                 goto error;
 292
 293         if (!isl_space_match(aff->ls->dim, isl_dim_param,
 294                              model, isl_dim_param)) {
 295                 isl_reordering *exp;
 296
 297                 model = isl_space_drop_dims(model, isl_dim_in,
 298                                         0, isl_space_dim(model, isl_dim_in));
 299                 model = isl_space_drop_dims(model, isl_dim_out,
 300                                         0, isl_space_dim(model, isl_dim_out));
 301                 exp = isl_parameter_alignment_reordering(aff->ls->dim, model);
 302                 exp = isl_reordering_extend_space(exp,
 303                                         isl_aff_get_domain_space(aff));
 304                 aff = isl_aff_realign_domain(aff, exp);
 305         }
 306
 307         isl_space_free(model);
 308         return aff;
 309 error:
 310         isl_space_free(model);
 311         isl_aff_free(aff);
 312         return NULL;
 313 }
 314
 315 int isl_aff_plain_is_zero(__isl_keep isl_aff *aff)
 316 {
 317         if (!aff)
 318                 return -1;
 319
 320         return isl_seq_first_non_zero(aff->v->el + 1, aff->v->size - 1) < 0;
 321 }
 322
 323 int isl_aff_plain_is_equal(__isl_keep isl_aff *aff1, __isl_keep isl_aff *aff2)
 324 {
 325         int equal;
 326
 327         if (!aff1 || !aff2)
 328                 return -1;
 329
 330         equal = isl_local_space_is_equal(aff1->ls, aff2->ls);
 331         if (equal < 0 || !equal)
 332                 return equal;
 333
 334         return isl_vec_is_equal(aff1->v, aff2->v);
 335 }
 336
 337 int isl_aff_get_denominator(__isl_keep isl_aff *aff, isl_int *v)
 338 {
 339         if (!aff)
 340                 return -1;
 341         isl_int_set(*v, aff->v->el[0]);
 342         return 0;
 343 }
 344
 345 int isl_aff_get_constant(__isl_keep isl_aff *aff, isl_int *v)
 346 {
 347         if (!aff)
 348                 return -1;
 349         isl_int_set(*v, aff->v->el[1]);
 350         return 0;
 351 }
 352
 353 int isl_aff_get_coefficient(__isl_keep isl_aff *aff,
 354         enum isl_dim_type type, int pos, isl_int *v)
 355 {
 356         if (!aff)
 357                 return -1;
 358
 359         if (type == isl_dim_out)
 360                 isl_die(aff->v->ctx, isl_error_invalid,
 361                         "output/set dimension does not have a coefficient",
 362                         return -1);
 363         if (type == isl_dim_in)
 364                 type = isl_dim_set;
 365
 366         if (pos >= isl_local_space_dim(aff->ls, type))
 367                 isl_die(aff->v->ctx, isl_error_invalid,
 368                         "position out of bounds", return -1);
 369
 370         pos += isl_local_space_offset(aff->ls, type);
 371         isl_int_set(*v, aff->v->el[1 + pos]);
 372
 373         return 0;
 374 }
 375
 376 __isl_give isl_aff *isl_aff_set_denominator(__isl_take isl_aff *aff, isl_int v)
 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_set(aff->v->el[0], v);
 387
 388         return aff;
 389 }
 390
 391 __isl_give isl_aff *isl_aff_set_constant(__isl_take isl_aff *aff, isl_int v)
 392 {
 393         aff = isl_aff_cow(aff);
 394         if (!aff)
 395                 return NULL;
 396
 397         aff->v = isl_vec_cow(aff->v);
 398         if (!aff->v)
 399                 return isl_aff_free(aff);
 400
 401         isl_int_set(aff->v->el[1], v);
 402
 403         return aff;
 404 }
 405
 406 __isl_give isl_aff *isl_aff_add_constant(__isl_take isl_aff *aff, isl_int v)
 407 {
 408         if (isl_int_is_zero(v))
 409                 return aff;
 410
 411         aff = isl_aff_cow(aff);
 412         if (!aff)
 413                 return NULL;
 414
 415         aff->v = isl_vec_cow(aff->v);
 416         if (!aff->v)
 417                 return isl_aff_free(aff);
 418
 419         isl_int_addmul(aff->v->el[1], aff->v->el[0], v);
 420
 421         return aff;
 422 }
 423
 424 __isl_give isl_aff *isl_aff_add_constant_si(__isl_take isl_aff *aff, int v)
 425 {
 426         isl_int t;
 427
 428         isl_int_init(t);
 429         isl_int_set_si(t, v);
 430         aff = isl_aff_add_constant(aff, t);
 431         isl_int_clear(t);
 432
 433         return aff;
 434 }
 435
 436 __isl_give isl_aff *isl_aff_set_constant_si(__isl_take isl_aff *aff, int v)
 437 {
 438         aff = isl_aff_cow(aff);
 439         if (!aff)
 440                 return NULL;
 441
 442         aff->v = isl_vec_cow(aff->v);
 443         if (!aff->v)
 444                 return isl_aff_free(aff);
 445
 446         isl_int_set_si(aff->v->el[1], v);
 447
 448         return aff;
 449 }
 450
 451 __isl_give isl_aff *isl_aff_set_coefficient(__isl_take isl_aff *aff,
 452         enum isl_dim_type type, int pos, isl_int v)
 453 {
 454         if (!aff)
 455                 return NULL;
 456
 457         if (type == isl_dim_out)
 458                 isl_die(aff->v->ctx, isl_error_invalid,
 459                         "output/set dimension does not have a coefficient",
 460                         return isl_aff_free(aff));
 461         if (type == isl_dim_in)
 462                 type = isl_dim_set;
 463
 464         if (pos >= isl_local_space_dim(aff->ls, type))
 465                 isl_die(aff->v->ctx, isl_error_invalid,
 466                         "position out of bounds", return isl_aff_free(aff));
 467
 468         aff = isl_aff_cow(aff);
 469         if (!aff)
 470                 return NULL;
 471
 472         aff->v = isl_vec_cow(aff->v);
 473         if (!aff->v)
 474                 return isl_aff_free(aff);
 475
 476         pos += isl_local_space_offset(aff->ls, type);
 477         isl_int_set(aff->v->el[1 + pos], v);
 478
 479         return aff;
 480 }
 481
 482 __isl_give isl_aff *isl_aff_set_coefficient_si(__isl_take isl_aff *aff,
 483         enum isl_dim_type type, int pos, int v)
 484 {
 485         if (!aff)
 486                 return NULL;
 487
 488         if (type == isl_dim_out)
 489                 isl_die(aff->v->ctx, isl_error_invalid,
 490                         "output/set dimension does not have a coefficient",
 491                         return isl_aff_free(aff));
 492         if (type == isl_dim_in)
 493                 type = isl_dim_set;
 494
 495         if (pos >= isl_local_space_dim(aff->ls, type))
 496                 isl_die(aff->v->ctx, isl_error_invalid,
 497                         "position out of bounds", return isl_aff_free(aff));
 498
 499         aff = isl_aff_cow(aff);
 500         if (!aff)
 501                 return NULL;
 502
 503         aff->v = isl_vec_cow(aff->v);
 504         if (!aff->v)
 505                 return isl_aff_free(aff);
 506
 507         pos += isl_local_space_offset(aff->ls, type);
 508         isl_int_set_si(aff->v->el[1 + pos], v);
 509
 510         return aff;
 511 }
 512
 513 __isl_give isl_aff *isl_aff_add_coefficient(__isl_take isl_aff *aff,
 514         enum isl_dim_type type, int pos, isl_int v)
 515 {
 516         if (!aff)
 517                 return NULL;
 518
 519         if (type == isl_dim_out)
 520                 isl_die(aff->v->ctx, isl_error_invalid,
 521                         "output/set dimension does not have a coefficient",
 522                         return isl_aff_free(aff));
 523         if (type == isl_dim_in)
 524                 type = isl_dim_set;
 525
 526         if (pos >= isl_local_space_dim(aff->ls, type))
 527                 isl_die(aff->v->ctx, isl_error_invalid,
 528                         "position out of bounds", return isl_aff_free(aff));
 529
 530         aff = isl_aff_cow(aff);
 531         if (!aff)
 532                 return NULL;
 533
 534         aff->v = isl_vec_cow(aff->v);
 535         if (!aff->v)
 536                 return isl_aff_free(aff);
 537
 538         pos += isl_local_space_offset(aff->ls, type);
 539         isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v);
 540
 541         return aff;
 542 }
 543
 544 __isl_give isl_aff *isl_aff_add_coefficient_si(__isl_take isl_aff *aff,
 545         enum isl_dim_type type, int pos, int v)
 546 {
 547         isl_int t;
 548
 549         isl_int_init(t);
 550         isl_int_set_si(t, v);
 551         aff = isl_aff_add_coefficient(aff, type, pos, t);
 552         isl_int_clear(t);
 553
 554         return aff;
 555 }
 556
 557 __isl_give isl_aff *isl_aff_get_div(__isl_keep isl_aff *aff, int pos)
 558 {
 559         if (!aff)
 560                 return NULL;
 561
 562         return isl_local_space_get_div(aff->ls, pos);
 563 }
 564
 565 __isl_give isl_aff *isl_aff_neg(__isl_take isl_aff *aff)
 566 {
 567         aff = isl_aff_cow(aff);
 568         if (!aff)
 569                 return NULL;
 570         aff->v = isl_vec_cow(aff->v);
 571         if (!aff->v)
 572                 return isl_aff_free(aff);
 573
 574         isl_seq_neg(aff->v->el + 1, aff->v->el + 1, aff->v->size - 1);
 575
 576         return aff;
 577 }
 578
 579 /* Remove divs from the local space that do not appear in the affine
 580  * expression.
 581  * We currently only remove divs at the end.
 582  * Some intermediate divs may also not appear directly in the affine
 583  * expression, but we would also need to check that no other divs are
 584  * defined in terms of them.
 585  */
 586 __isl_give isl_aff *isl_aff_remove_unused_divs( __isl_take isl_aff *aff)
 587 {
 588         int pos;
 589         int off;
 590         int n;
 591
 592         if (!aff)
 593                 return NULL;
 594
 595         n = isl_local_space_dim(aff->ls, isl_dim_div);
 596         off = isl_local_space_offset(aff->ls, isl_dim_div);
 597
 598         pos = isl_seq_last_non_zero(aff->v->el + 1 + off, n) + 1;
 599         if (pos == n)
 600                 return aff;
 601
 602         aff = isl_aff_cow(aff);
 603         if (!aff)
 604                 return NULL;
 605
 606         aff->ls = isl_local_space_drop_dims(aff->ls, isl_dim_div, pos, n - pos);
 607         aff->v = isl_vec_drop_els(aff->v, 1 + off + pos, n - pos);
 608         if (!aff->ls || !aff->v)
 609                 return isl_aff_free(aff);
 610
 611         return aff;
 612 }
 613
 614 __isl_give isl_aff *isl_aff_normalize(__isl_take isl_aff *aff)
 615 {
 616         if (!aff)
 617                 return NULL;
 618         aff->v = isl_vec_normalize(aff->v);
 619         if (!aff->v)
 620                 return isl_aff_free(aff);
 621         aff = isl_aff_remove_unused_divs(aff);
 622         return aff;
 623 }
 624
 625 /* Given f, return floor(f).
 626  * If f is an integer expression, then just return f.
 627  * Otherwise, if f = g/m, write g = q m + r,
 628  * create a new div d = [r/m] and return the expression q + d.
 629  * The coefficients in r are taken to lie between -m/2 and m/2.
 630  */
 631 __isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff)
 632 {
 633         int i;
 634         int size;
 635         isl_ctx *ctx;
 636         isl_vec *div;
 637
 638         if (!aff)
 639                 return NULL;
 640
 641         if (isl_int_is_one(aff->v->el[0]))
 642                 return aff;
 643
 644         aff = isl_aff_cow(aff);
 645         if (!aff)
 646                 return NULL;
 647
 648         aff->v = isl_vec_cow(aff->v);
 649         div = isl_vec_copy(aff->v);
 650         div = isl_vec_cow(div);
 651         if (!div)
 652                 return isl_aff_free(aff);
 653
 654         ctx = isl_aff_get_ctx(aff);
 655         isl_int_fdiv_q(aff->v->el[0], aff->v->el[0], ctx->two);
 656         for (i = 1; i < aff->v->size; ++i) {
 657                 isl_int_fdiv_r(div->el[i], div->el[i], div->el[0]);
 658                 isl_int_fdiv_q(aff->v->el[i], aff->v->el[i], div->el[0]);
 659                 if (isl_int_gt(div->el[i], aff->v->el[0])) {
 660                         isl_int_sub(div->el[i], div->el[i], div->el[0]);
 661                         isl_int_add_ui(aff->v->el[i], aff->v->el[i], 1);
 662                 }
 663         }
 664
 665         aff->ls = isl_local_space_add_div(aff->ls, div);
 666         if (!aff->ls)
 667                 return isl_aff_free(aff);
 668
 669         size = aff->v->size;
 670         aff->v = isl_vec_extend(aff->v, size + 1);
 671         if (!aff->v)
 672                 return isl_aff_free(aff);
 673         isl_int_set_si(aff->v->el[0], 1);
 674         isl_int_set_si(aff->v->el[size], 1);
 675
 676         return aff;
 677 }
 678
 679 /* Compute
 680  *
 681  *      aff mod m = aff - m * floor(aff/m)
 682  */
 683 __isl_give isl_aff *isl_aff_mod(__isl_take isl_aff *aff, isl_int m)
 684 {
 685         isl_aff *res;
 686
 687         res = isl_aff_copy(aff);
 688         aff = isl_aff_scale_down(aff, m);
 689         aff = isl_aff_floor(aff);
 690         aff = isl_aff_scale(aff, m);
 691         res = isl_aff_sub(res, aff);
 692
 693         return res;
 694 }
 695
 696 /* Compute
 697  *
 698  *      pwaff mod m = pwaff - m * floor(pwaff/m)
 699  */
 700 __isl_give isl_pw_aff *isl_pw_aff_mod(__isl_take isl_pw_aff *pwaff, isl_int m)
 701 {
 702         isl_pw_aff *res;
 703
 704         res = isl_pw_aff_copy(pwaff);
 705         pwaff = isl_pw_aff_scale_down(pwaff, m);
 706         pwaff = isl_pw_aff_floor(pwaff);
 707         pwaff = isl_pw_aff_scale(pwaff, m);
 708         res = isl_pw_aff_sub(res, pwaff);
 709
 710         return res;
 711 }
 712
 713 /* Given f, return ceil(f).
 714  * If f is an integer expression, then just return f.
 715  * Otherwise, create a new div d = [-f] and return the expression -d.
 716  */
 717 __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff)
 718 {
 719         if (!aff)
 720                 return NULL;
 721
 722         if (isl_int_is_one(aff->v->el[0]))
 723                 return aff;
 724
 725         aff = isl_aff_neg(aff);
 726         aff = isl_aff_floor(aff);
 727         aff = isl_aff_neg(aff);
 728
 729         return aff;
 730 }
 731
 732 /* Apply the expansion computed by isl_merge_divs.
 733  * The expansion itself is given by "exp" while the resulting
 734  * list of divs is given by "div".
 735  */
 736 __isl_give isl_aff *isl_aff_expand_divs( __isl_take isl_aff *aff,
 737         __isl_take isl_mat *div, int *exp)
 738 {
 739         int i, j;
 740         int old_n_div;
 741         int new_n_div;
 742         int offset;
 743
 744         aff = isl_aff_cow(aff);
 745         if (!aff || !div)
 746                 goto error;
 747
 748         old_n_div = isl_local_space_dim(aff->ls, isl_dim_div);
 749         new_n_div = isl_mat_rows(div);
 750         if (new_n_div < old_n_div)
 751                 isl_die(isl_mat_get_ctx(div), isl_error_invalid,
 752                         "not an expansion", goto error);
 753
 754         aff->v = isl_vec_extend(aff->v, aff->v->size + new_n_div - old_n_div);
 755         if (!aff->v)
 756                 goto error;
 757
 758         offset = 1 + isl_local_space_offset(aff->ls, isl_dim_div);
 759         j = old_n_div - 1;
 760         for (i = new_n_div - 1; i >= 0; --i) {
 761                 if (j >= 0 && exp[j] == i) {
 762                         if (i != j)
 763                                 isl_int_swap(aff->v->el[offset + i],
 764                                              aff->v->el[offset + j]);
 765                         j--;
 766                 } else
 767                         isl_int_set_si(aff->v->el[offset + i], 0);
 768         }
 769
 770         aff->ls = isl_local_space_replace_divs(aff->ls, isl_mat_copy(div));
 771         if (!aff->ls)
 772                 goto error;
 773         isl_mat_free(div);
 774         return aff;
 775 error:
 776         isl_aff_free(aff);
 777         isl_mat_free(div);
 778         return NULL;
 779 }
 780
 781 /* Add two affine expressions that live in the same local space.
 782  */
 783 static __isl_give isl_aff *add_expanded(__isl_take isl_aff *aff1,
 784         __isl_take isl_aff *aff2)
 785 {
 786         isl_int gcd, f;
 787
 788         aff1 = isl_aff_cow(aff1);
 789         if (!aff1 || !aff2)
 790                 goto error;
 791
 792         aff1->v = isl_vec_cow(aff1->v);
 793         if (!aff1->v)
 794                 goto error;
 795
 796         isl_int_init(gcd);
 797         isl_int_init(f);
 798         isl_int_gcd(gcd, aff1->v->el[0], aff2->v->el[0]);
 799         isl_int_divexact(f, aff2->v->el[0], gcd);
 800         isl_seq_scale(aff1->v->el + 1, aff1->v->el + 1, f, aff1->v->size - 1);
 801         isl_int_divexact(f, aff1->v->el[0], gcd);
 802         isl_seq_addmul(aff1->v->el + 1, f, aff2->v->el + 1, aff1->v->size - 1);
 803         isl_int_divexact(f, aff2->v->el[0], gcd);
 804         isl_int_mul(aff1->v->el[0], aff1->v->el[0], f);
 805         isl_int_clear(f);
 806         isl_int_clear(gcd);
 807
 808         isl_aff_free(aff2);
 809         return aff1;
 810 error:
 811         isl_aff_free(aff1);
 812         isl_aff_free(aff2);
 813         return NULL;
 814 }
 815
 816 __isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
 817         __isl_take isl_aff *aff2)
 818 {
 819         isl_ctx *ctx;
 820         int *exp1 = NULL;
 821         int *exp2 = NULL;
 822         isl_mat *div;
 823
 824         if (!aff1 || !aff2)
 825                 goto error;
 826
 827         ctx = isl_aff_get_ctx(aff1);
 828         if (!isl_space_is_equal(aff1->ls->dim, aff2->ls->dim))
 829                 isl_die(ctx, isl_error_invalid,
 830                         "spaces don't match", goto error);
 831
 832         if (aff1->ls->div->n_row == 0 && aff2->ls->div->n_row == 0)
 833                 return add_expanded(aff1, aff2);
 834
 835         exp1 = isl_alloc_array(ctx, int, aff1->ls->div->n_row);
 836         exp2 = isl_alloc_array(ctx, int, aff2->ls->div->n_row);
 837         if (!exp1 || !exp2)
 838                 goto error;
 839
 840         div = isl_merge_divs(aff1->ls->div, aff2->ls->div, exp1, exp2);
 841         aff1 = isl_aff_expand_divs(aff1, isl_mat_copy(div), exp1);
 842         aff2 = isl_aff_expand_divs(aff2, div, exp2);
 843         free(exp1);
 844         free(exp2);
 845
 846         return add_expanded(aff1, aff2);
 847 error:
 848         free(exp1);
 849         free(exp2);
 850         isl_aff_free(aff1);
 851         isl_aff_free(aff2);
 852         return NULL;
 853 }
 854
 855 __isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
 856         __isl_take isl_aff *aff2)
 857 {
 858         return isl_aff_add(aff1, isl_aff_neg(aff2));
 859 }
 860
 861 __isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f)
 862 {
 863         isl_int gcd;
 864
 865         if (isl_int_is_one(f))
 866                 return aff;
 867
 868         aff = isl_aff_cow(aff);
 869         if (!aff)
 870                 return NULL;
 871         aff->v = isl_vec_cow(aff->v);
 872         if (!aff->v)
 873                 return isl_aff_free(aff);
 874
 875         isl_int_init(gcd);
 876         isl_int_gcd(gcd, aff->v->el[0], f);
 877         isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd);
 878         isl_int_divexact(gcd, f, gcd);
 879         isl_seq_scale(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
 880         isl_int_clear(gcd);
 881
 882         return aff;
 883 }
 884
 885 __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f)
 886 {
 887         isl_int gcd;
 888
 889         if (isl_int_is_one(f))
 890                 return aff;
 891
 892         aff = isl_aff_cow(aff);
 893         if (!aff)
 894                 return NULL;
 895         aff->v = isl_vec_cow(aff->v);
 896         if (!aff->v)
 897                 return isl_aff_free(aff);
 898
 899         isl_int_init(gcd);
 900         isl_seq_gcd(aff->v->el + 1, aff->v->size - 1, &gcd);
 901         isl_int_gcd(gcd, gcd, f);
 902         isl_seq_scale_down(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
 903         isl_int_divexact(gcd, f, gcd);
 904         isl_int_mul(aff->v->el[0], aff->v->el[0], gcd);
 905         isl_int_clear(gcd);
 906
 907         return aff;
 908 }
 909
 910 __isl_give isl_aff *isl_aff_scale_down_ui(__isl_take isl_aff *aff, unsigned f)
 911 {
 912         isl_int v;
 913
 914         if (f == 1)
 915                 return aff;
 916
 917         isl_int_init(v);
 918         isl_int_set_ui(v, f);
 919         aff = isl_aff_scale_down(aff, v);
 920         isl_int_clear(v);
 921
 922         return aff;
 923 }
 924
 925 __isl_give isl_aff *isl_aff_set_dim_name(__isl_take isl_aff *aff,
 926         enum isl_dim_type type, unsigned pos, const char *s)
 927 {
 928         aff = isl_aff_cow(aff);
 929         if (!aff)
 930                 return NULL;
 931         if (type == isl_dim_out)
 932                 isl_die(aff->v->ctx, isl_error_invalid,
 933                         "cannot set name of output/set dimension",
 934                         return isl_aff_free(aff));
 935         if (type == isl_dim_in)
 936                 type = isl_dim_set;
 937         aff->ls = isl_local_space_set_dim_name(aff->ls, type, pos, s);
 938         if (!aff->ls)
 939                 return isl_aff_free(aff);
 940
 941         return aff;
 942 }
 943
 944 __isl_give isl_aff *isl_aff_set_dim_id(__isl_take isl_aff *aff,
 945         enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
 946 {
 947         aff = isl_aff_cow(aff);
 948         if (!aff)
 949                 return isl_id_free(id);
 950         if (type == isl_dim_out)
 951                 isl_die(aff->v->ctx, isl_error_invalid,
 952                         "cannot set name of output/set dimension",
 953                         goto error);
 954         if (type == isl_dim_in)
 955                 type = isl_dim_set;
 956         aff->ls = isl_local_space_set_dim_id(aff->ls, type, pos, id);
 957         if (!aff->ls)
 958                 return isl_aff_free(aff);
 959
 960         return aff;
 961 error:
 962         isl_id_free(id);
 963         isl_aff_free(aff);
 964         return NULL;
 965 }
 966
 967 /* Exploit the equalities in "eq" to simplify the affine expression
 968  * and the expressions of the integer divisions in the local space.
 969  * The integer divisions in this local space are assumed to appear
 970  * as regular dimensions in "eq".
 971  */
 972 static __isl_give isl_aff *isl_aff_substitute_equalities_lifted(
 973         __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
 974 {
 975         int i, j;
 976         unsigned total;
 977         unsigned n_div;
 978
 979         if (!eq)
 980                 goto error;
 981         if (eq->n_eq == 0) {
 982                 isl_basic_set_free(eq);
 983                 return aff;
 984         }
 985
 986         aff = isl_aff_cow(aff);
 987         if (!aff)
 988                 goto error;
 989
 990         aff->ls = isl_local_space_substitute_equalities(aff->ls,
 991                                                         isl_basic_set_copy(eq));
 992         if (!aff->ls)
 993                 goto error;
 994
 995         total = 1 + isl_space_dim(eq->dim, isl_dim_all);
 996         n_div = eq->n_div;
 997         for (i = 0; i < eq->n_eq; ++i) {
 998                 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
 999                 if (j < 0 || j == 0 || j >= total)
1000                         continue;
1001
1002                 isl_seq_elim(aff->v->el + 1, eq->eq[i], j, total,
1003                                 &aff->v->el[0]);
1004         }
1005
1006         isl_basic_set_free(eq);
1007         aff = isl_aff_normalize(aff);
1008         return aff;
1009 error:
1010         isl_basic_set_free(eq);
1011         isl_aff_free(aff);
1012         return NULL;
1013 }
1014
1015 /* Exploit the equalities in "eq" to simplify the affine expression
1016  * and the expressions of the integer divisions in the local space.
1017  */
1018 static __isl_give isl_aff *isl_aff_substitute_equalities(
1019         __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
1020 {
1021         int n_div;
1022
1023         if (!aff || !eq)
1024                 goto error;
1025         n_div = isl_local_space_dim(aff->ls, isl_dim_div);
1026         if (n_div > 0)
1027                 eq = isl_basic_set_add(eq, isl_dim_set, n_div);
1028         return isl_aff_substitute_equalities_lifted(aff, eq);
1029 error:
1030         isl_basic_set_free(eq);
1031         isl_aff_free(aff);
1032         return NULL;
1033 }
1034
1035 /* Look for equalities among the variables shared by context and aff
1036  * and the integer divisions of aff, if any.
1037  * The equalities are then used to eliminate coefficients and/or integer
1038  * divisions from aff.
1039  */
1040 __isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff,
1041         __isl_take isl_set *context)
1042 {
1043         isl_basic_set *hull;
1044         int n_div;
1045
1046         if (!aff)
1047                 goto error;
1048         n_div = isl_local_space_dim(aff->ls, isl_dim_div);
1049         if (n_div > 0) {
1050                 isl_basic_set *bset;
1051                 isl_local_space *ls;
1052                 context = isl_set_add_dims(context, isl_dim_set, n_div);
1053                 ls = isl_aff_get_domain_local_space(aff);
1054                 bset = isl_basic_set_from_local_space(ls);
1055                 bset = isl_basic_set_lift(bset);
1056                 bset = isl_basic_set_flatten(bset);
1057                 context = isl_set_intersect(context,
1058                                             isl_set_from_basic_set(bset));
1059         }
1060
1061         hull = isl_set_affine_hull(context);
1062         return isl_aff_substitute_equalities_lifted(aff, hull);
1063 error:
1064         isl_aff_free(aff);
1065         isl_set_free(context);
1066         return NULL;
1067 }
1068
1069 __isl_give isl_aff *isl_aff_gist_params(__isl_take isl_aff *aff,
1070         __isl_take isl_set *context)
1071 {
1072         isl_set *dom_context = isl_set_universe(isl_aff_get_domain_space(aff));
1073         dom_context = isl_set_intersect_params(dom_context, context);
1074         return isl_aff_gist(aff, dom_context);
1075 }
1076
1077 /* Return a basic set containing those elements in the space
1078  * of aff where it is non-negative.
1079  */
1080 __isl_give isl_basic_set *isl_aff_nonneg_basic_set(__isl_take isl_aff *aff)
1081 {
1082         isl_constraint *ineq;
1083         isl_basic_set *bset;
1084
1085         ineq = isl_inequality_from_aff(aff);
1086
1087         bset = isl_basic_set_from_constraint(ineq);
1088         bset = isl_basic_set_simplify(bset);
1089         return bset;
1090 }
1091
1092 /* Return a basic set containing those elements in the space
1093  * of aff where it is zero.
1094  */
1095 __isl_give isl_basic_set *isl_aff_zero_basic_set(__isl_take isl_aff *aff)
1096 {
1097         isl_constraint *ineq;
1098         isl_basic_set *bset;
1099
1100         ineq = isl_equality_from_aff(aff);
1101
1102         bset = isl_basic_set_from_constraint(ineq);
1103         bset = isl_basic_set_simplify(bset);
1104         return bset;
1105 }
1106
1107 /* Return a basic set containing those elements in the shared space
1108  * of aff1 and aff2 where aff1 is greater than or equal to aff2.
1109  */
1110 __isl_give isl_basic_set *isl_aff_ge_basic_set(__isl_take isl_aff *aff1,
1111         __isl_take isl_aff *aff2)
1112 {
1113         aff1 = isl_aff_sub(aff1, aff2);
1114
1115         return isl_aff_nonneg_basic_set(aff1);
1116 }
1117
1118 /* Return a basic set containing those elements in the shared space
1119  * of aff1 and aff2 where aff1 is smaller than or equal to aff2.
1120  */
1121 __isl_give isl_basic_set *isl_aff_le_basic_set(__isl_take isl_aff *aff1,
1122         __isl_take isl_aff *aff2)
1123 {
1124         return isl_aff_ge_basic_set(aff2, aff1);
1125 }
1126
1127 __isl_give isl_aff *isl_aff_add_on_domain(__isl_keep isl_set *dom,
1128         __isl_take isl_aff *aff1, __isl_take isl_aff *aff2)
1129 {
1130         aff1 = isl_aff_add(aff1, aff2);
1131         aff1 = isl_aff_gist(aff1, isl_set_copy(dom));
1132         return aff1;
1133 }
1134
1135 int isl_aff_is_empty(__isl_keep isl_aff *aff)
1136 {
1137         if (!aff)
1138                 return -1;
1139
1140         return 0;
1141 }
1142
1143 /* Check whether the given affine expression has non-zero coefficient
1144  * for any dimension in the given range or if any of these dimensions
1145  * appear with non-zero coefficients in any of the integer divisions
1146  * involved in the affine expression.
1147  */
1148 int isl_aff_involves_dims(__isl_keep isl_aff *aff,
1149         enum isl_dim_type type, unsigned first, unsigned n)
1150 {
1151         int i;
1152         isl_ctx *ctx;
1153         int *active = NULL;
1154         int involves = 0;
1155
1156         if (!aff)
1157                 return -1;
1158         if (n == 0)
1159                 return 0;
1160
1161         ctx = isl_aff_get_ctx(aff);
1162         if (first + n > isl_aff_dim(aff, type))
1163                 isl_die(ctx, isl_error_invalid,
1164                         "range out of bounds", return -1);
1165
1166         active = isl_local_space_get_active(aff->ls, aff->v->el + 2);
1167         if (!active)
1168                 goto error;
1169
1170         first += isl_local_space_offset(aff->ls, type) - 1;
1171         for (i = 0; i < n; ++i)
1172                 if (active[first + i]) {
1173                         involves = 1;
1174                         break;
1175                 }
1176
1177         free(active);
1178
1179         return involves;
1180 error:
1181         free(active);
1182         return -1;
1183 }
1184
1185 __isl_give isl_aff *isl_aff_drop_dims(__isl_take isl_aff *aff,
1186         enum isl_dim_type type, unsigned first, unsigned n)
1187 {
1188         isl_ctx *ctx;
1189
1190         if (!aff)
1191                 return NULL;
1192         if (type == isl_dim_out)
1193                 isl_die(aff->v->ctx, isl_error_invalid,
1194                         "cannot drop output/set dimension",
1195                         return isl_aff_free(aff));
1196         if (type == isl_dim_in)
1197                 type = isl_dim_set;
1198         if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
1199                 return aff;
1200
1201         ctx = isl_aff_get_ctx(aff);
1202         if (first + n > isl_local_space_dim(aff->ls, type))
1203                 isl_die(ctx, isl_error_invalid, "range out of bounds",
1204                         return isl_aff_free(aff));
1205
1206         aff = isl_aff_cow(aff);
1207         if (!aff)
1208                 return NULL;
1209
1210         aff->ls = isl_local_space_drop_dims(aff->ls, type, first, n);
1211         if (!aff->ls)
1212                 return isl_aff_free(aff);
1213
1214         first += 1 + isl_local_space_offset(aff->ls, type);
1215         aff->v = isl_vec_drop_els(aff->v, first, n);
1216         if (!aff->v)
1217                 return isl_aff_free(aff);
1218
1219         return aff;
1220 }
1221
1222 /* Project the domain of the affine expression onto its parameter space.
1223  * The affine expression may not involve any of the domain dimensions.
1224  */
1225 __isl_give isl_aff *isl_aff_project_domain_on_params(__isl_take isl_aff *aff)
1226 {
1227         isl_space *space;
1228         unsigned n;
1229         int involves;
1230
1231         n = isl_aff_dim(aff, isl_dim_in);
1232         involves = isl_aff_involves_dims(aff, isl_dim_in, 0, n);
1233         if (involves < 0)
1234                 return isl_aff_free(aff);
1235         if (involves)
1236                 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
1237                     "affine expression involves some of the domain dimensions",
1238                     return isl_aff_free(aff));
1239         aff = isl_aff_drop_dims(aff, isl_dim_in, 0, n);
1240         space = isl_aff_get_domain_space(aff);
1241         space = isl_space_params(space);
1242         aff = isl_aff_reset_domain_space(aff, space);
1243         return aff;
1244 }
1245
1246 __isl_give isl_aff *isl_aff_insert_dims(__isl_take isl_aff *aff,
1247         enum isl_dim_type type, unsigned first, unsigned n)
1248 {
1249         isl_ctx *ctx;
1250
1251         if (!aff)
1252                 return NULL;
1253         if (type == isl_dim_out)
1254                 isl_die(aff->v->ctx, isl_error_invalid,
1255                         "cannot insert output/set dimensions",
1256                         return isl_aff_free(aff));
1257         if (type == isl_dim_in)
1258                 type = isl_dim_set;
1259         if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
1260                 return aff;
1261
1262         ctx = isl_aff_get_ctx(aff);
1263         if (first > isl_local_space_dim(aff->ls, type))
1264                 isl_die(ctx, isl_error_invalid, "position out of bounds",
1265                         return isl_aff_free(aff));
1266
1267         aff = isl_aff_cow(aff);
1268         if (!aff)
1269                 return NULL;
1270
1271         aff->ls = isl_local_space_insert_dims(aff->ls, type, first, n);
1272         if (!aff->ls)
1273                 return isl_aff_free(aff);
1274
1275         first += 1 + isl_local_space_offset(aff->ls, type);
1276         aff->v = isl_vec_insert_zero_els(aff->v, first, n);
1277         if (!aff->v)
1278                 return isl_aff_free(aff);
1279
1280         return aff;
1281 }
1282
1283 __isl_give isl_aff *isl_aff_add_dims(__isl_take isl_aff *aff,
1284         enum isl_dim_type type, unsigned n)
1285 {
1286         unsigned pos;
1287
1288         pos = isl_aff_dim(aff, type);
1289
1290         return isl_aff_insert_dims(aff, type, pos, n);
1291 }
1292
1293 __isl_give isl_pw_aff *isl_pw_aff_add_dims(__isl_take isl_pw_aff *pwaff,
1294         enum isl_dim_type type, unsigned n)
1295 {
1296         unsigned pos;
1297
1298         pos = isl_pw_aff_dim(pwaff, type);
1299
1300         return isl_pw_aff_insert_dims(pwaff, type, pos, n);
1301 }
1302
1303 __isl_give isl_pw_aff *isl_pw_aff_from_aff(__isl_take isl_aff *aff)
1304 {
1305         isl_set *dom = isl_set_universe(isl_aff_get_domain_space(aff));
1306         return isl_pw_aff_alloc(dom, aff);
1307 }
1308
1309 #undef PW
1310 #define PW isl_pw_aff
1311 #undef EL
1312 #define EL isl_aff
1313 #undef EL_IS_ZERO
1314 #define EL_IS_ZERO is_empty
1315 #undef ZERO
1316 #define ZERO empty
1317 #undef IS_ZERO
1318 #define IS_ZERO is_empty
1319 #undef FIELD
1320 #define FIELD aff
1321 #undef DEFAULT_IS_ZERO
1322 #define DEFAULT_IS_ZERO 0
1323
1324 #define NO_EVAL
1325 #define NO_OPT
1326 #define NO_MOVE_DIMS
1327 #define NO_LIFT
1328 #define NO_MORPH
1329
1330 #include <isl_pw_templ.c>
1331
1332 static __isl_give isl_set *align_params_pw_pw_set_and(
1333         __isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2,
1334         __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1335                                     __isl_take isl_pw_aff *pwaff2))
1336 {
1337         if (!pwaff1 || !pwaff2)
1338                 goto error;
1339         if (isl_space_match(pwaff1->dim, isl_dim_param,
1340                           pwaff2->dim, isl_dim_param))
1341                 return fn(pwaff1, pwaff2);
1342         if (!isl_space_has_named_params(pwaff1->dim) ||
1343             !isl_space_has_named_params(pwaff2->dim))
1344                 isl_die(isl_pw_aff_get_ctx(pwaff1), isl_error_invalid,
1345                         "unaligned unnamed parameters", goto error);
1346         pwaff1 = isl_pw_aff_align_params(pwaff1, isl_pw_aff_get_space(pwaff2));
1347         pwaff2 = isl_pw_aff_align_params(pwaff2, isl_pw_aff_get_space(pwaff1));
1348         return fn(pwaff1, pwaff2);
1349 error:
1350         isl_pw_aff_free(pwaff1);
1351         isl_pw_aff_free(pwaff2);
1352         return NULL;
1353 }
1354
1355 /* Compute a piecewise quasi-affine expression with a domain that
1356  * is the union of those of pwaff1 and pwaff2 and such that on each
1357  * cell, the quasi-affine expression is the better (according to cmp)
1358  * of those of pwaff1 and pwaff2.  If only one of pwaff1 or pwaff2
1359  * is defined on a given cell, then the associated expression
1360  * is the defined one.
1361  */
1362 static __isl_give isl_pw_aff *pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1363         __isl_take isl_pw_aff *pwaff2,
1364         __isl_give isl_basic_set *(*cmp)(__isl_take isl_aff *aff1,
1365                                         __isl_take isl_aff *aff2))
1366 {
1367         int i, j, n;
1368         isl_pw_aff *res;
1369         isl_ctx *ctx;
1370         isl_set *set;
1371
1372         if (!pwaff1 || !pwaff2)
1373                 goto error;
1374
1375         ctx = isl_space_get_ctx(pwaff1->dim);
1376         if (!isl_space_is_equal(pwaff1->dim, pwaff2->dim))
1377                 isl_die(ctx, isl_error_invalid,
1378                         "arguments should live in same space", goto error);
1379
1380         if (isl_pw_aff_is_empty(pwaff1)) {
1381                 isl_pw_aff_free(pwaff1);
1382                 return pwaff2;
1383         }
1384
1385         if (isl_pw_aff_is_empty(pwaff2)) {
1386                 isl_pw_aff_free(pwaff2);
1387                 return pwaff1;
1388         }
1389
1390         n = 2 * (pwaff1->n + 1) * (pwaff2->n + 1);
1391         res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n);
1392
1393         for (i = 0; i < pwaff1->n; ++i) {
1394                 set = isl_set_copy(pwaff1->p[i].set);
1395                 for (j = 0; j < pwaff2->n; ++j) {
1396                         struct isl_set *common;
1397                         isl_set *better;
1398
1399                         common = isl_set_intersect(
1400                                         isl_set_copy(pwaff1->p[i].set),
1401                                         isl_set_copy(pwaff2->p[j].set));
1402                         better = isl_set_from_basic_set(cmp(
1403                                         isl_aff_copy(pwaff2->p[j].aff),
1404                                         isl_aff_copy(pwaff1->p[i].aff)));
1405                         better = isl_set_intersect(common, better);
1406                         if (isl_set_plain_is_empty(better)) {
1407                                 isl_set_free(better);
1408                                 continue;
1409                         }
1410                         set = isl_set_subtract(set, isl_set_copy(better));
1411
1412                         res = isl_pw_aff_add_piece(res, better,
1413                                                 isl_aff_copy(pwaff2->p[j].aff));
1414                 }
1415                 res = isl_pw_aff_add_piece(res, set,
1416                                                 isl_aff_copy(pwaff1->p[i].aff));
1417         }
1418
1419         for (j = 0; j < pwaff2->n; ++j) {
1420                 set = isl_set_copy(pwaff2->p[j].set);
1421                 for (i = 0; i < pwaff1->n; ++i)
1422                         set = isl_set_subtract(set,
1423                                         isl_set_copy(pwaff1->p[i].set));
1424                 res = isl_pw_aff_add_piece(res, set,
1425                                                 isl_aff_copy(pwaff2->p[j].aff));
1426         }
1427
1428         isl_pw_aff_free(pwaff1);
1429         isl_pw_aff_free(pwaff2);
1430
1431         return res;
1432 error:
1433         isl_pw_aff_free(pwaff1);
1434         isl_pw_aff_free(pwaff2);
1435         return NULL;
1436 }
1437
1438 /* Compute a piecewise quasi-affine expression with a domain that
1439  * is the union of those of pwaff1 and pwaff2 and such that on each
1440  * cell, the quasi-affine expression is the maximum of those of pwaff1
1441  * and pwaff2.  If only one of pwaff1 or pwaff2 is defined on a given
1442  * cell, then the associated expression is the defined one.
1443  */
1444 static __isl_give isl_pw_aff *pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1445         __isl_take isl_pw_aff *pwaff2)
1446 {
1447         return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_ge_basic_set);
1448 }
1449
1450 __isl_give isl_pw_aff *isl_pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1451         __isl_take isl_pw_aff *pwaff2)
1452 {
1453         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2,
1454                                                         &pw_aff_union_max);
1455 }
1456
1457 /* Compute a piecewise quasi-affine expression with a domain that
1458  * is the union of those of pwaff1 and pwaff2 and such that on each
1459  * cell, the quasi-affine expression is the minimum of those of pwaff1
1460  * and pwaff2.  If only one of pwaff1 or pwaff2 is defined on a given
1461  * cell, then the associated expression is the defined one.
1462  */
1463 static __isl_give isl_pw_aff *pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1464         __isl_take isl_pw_aff *pwaff2)
1465 {
1466         return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_le_basic_set);
1467 }
1468
1469 __isl_give isl_pw_aff *isl_pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1470         __isl_take isl_pw_aff *pwaff2)
1471 {
1472         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2,
1473                                                         &pw_aff_union_min);
1474 }
1475
1476 __isl_give isl_pw_aff *isl_pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1477         __isl_take isl_pw_aff *pwaff2, int max)
1478 {
1479         if (max)
1480                 return isl_pw_aff_union_max(pwaff1, pwaff2);
1481         else
1482                 return isl_pw_aff_union_min(pwaff1, pwaff2);
1483 }
1484
1485 /* Construct a map with as domain the domain of pwaff and
1486  * one-dimensional range corresponding to the affine expressions.
1487  */
1488 static __isl_give isl_map *map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1489 {
1490         int i;
1491         isl_space *dim;
1492         isl_map *map;
1493
1494         if (!pwaff)
1495                 return NULL;
1496
1497         dim = isl_pw_aff_get_space(pwaff);
1498         map = isl_map_empty(dim);
1499
1500         for (i = 0; i < pwaff->n; ++i) {
1501                 isl_basic_map *bmap;
1502                 isl_map *map_i;
1503
1504                 bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
1505                 map_i = isl_map_from_basic_map(bmap);
1506                 map_i = isl_map_intersect_domain(map_i,
1507                                                 isl_set_copy(pwaff->p[i].set));
1508                 map = isl_map_union_disjoint(map, map_i);
1509         }
1510
1511         isl_pw_aff_free(pwaff);
1512
1513         return map;
1514 }
1515
1516 /* Construct a map with as domain the domain of pwaff and
1517  * one-dimensional range corresponding to the affine expressions.
1518  */
1519 __isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1520 {
1521         if (!pwaff)
1522                 return NULL;
1523         if (isl_space_is_set(pwaff->dim))
1524                 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1525                         "space of input is not a map",
1526                         return isl_pw_aff_free(pwaff));
1527         return map_from_pw_aff(pwaff);
1528 }
1529
1530 /* Construct a one-dimensional set with as parameter domain
1531  * the domain of pwaff and the single set dimension
1532  * corresponding to the affine expressions.
1533  */
1534 __isl_give isl_set *isl_set_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1535 {
1536         if (!pwaff)
1537                 return NULL;
1538         if (!isl_space_is_set(pwaff->dim))
1539                 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1540                         "space of input is not a set",
1541                         return isl_pw_aff_free(pwaff));
1542         return map_from_pw_aff(pwaff);
1543 }
1544
1545 /* Return a set containing those elements in the domain
1546  * of pwaff where it is non-negative.
1547  */
1548 __isl_give isl_set *isl_pw_aff_nonneg_set(__isl_take isl_pw_aff *pwaff)
1549 {
1550         int i;
1551         isl_set *set;
1552
1553         if (!pwaff)
1554                 return NULL;
1555
1556         set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1557
1558         for (i = 0; i < pwaff->n; ++i) {
1559                 isl_basic_set *bset;
1560                 isl_set *set_i;
1561
1562                 bset = isl_aff_nonneg_basic_set(isl_aff_copy(pwaff->p[i].aff));
1563                 set_i = isl_set_from_basic_set(bset);
1564                 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1565                 set = isl_set_union_disjoint(set, set_i);
1566         }
1567
1568         isl_pw_aff_free(pwaff);
1569
1570         return set;
1571 }
1572
1573 /* Return a set containing those elements in the domain
1574  * of pwaff where it is zero (if complement is 0) or not zero
1575  * (if complement is 1).
1576  */
1577 static __isl_give isl_set *pw_aff_zero_set(__isl_take isl_pw_aff *pwaff,
1578         int complement)
1579 {
1580         int i;
1581         isl_set *set;
1582
1583         if (!pwaff)
1584                 return NULL;
1585
1586         set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1587
1588         for (i = 0; i < pwaff->n; ++i) {
1589                 isl_basic_set *bset;
1590                 isl_set *set_i, *zero;
1591
1592                 bset = isl_aff_zero_basic_set(isl_aff_copy(pwaff->p[i].aff));
1593                 zero = isl_set_from_basic_set(bset);
1594                 set_i = isl_set_copy(pwaff->p[i].set);
1595                 if (complement)
1596                         set_i = isl_set_subtract(set_i, zero);
1597                 else
1598                         set_i = isl_set_intersect(set_i, zero);
1599                 set = isl_set_union_disjoint(set, set_i);
1600         }
1601
1602         isl_pw_aff_free(pwaff);
1603
1604         return set;
1605 }
1606
1607 /* Return a set containing those elements in the domain
1608  * of pwaff where it is zero.
1609  */
1610 __isl_give isl_set *isl_pw_aff_zero_set(__isl_take isl_pw_aff *pwaff)
1611 {
1612         return pw_aff_zero_set(pwaff, 0);
1613 }
1614
1615 /* Return a set containing those elements in the domain
1616  * of pwaff where it is not zero.
1617  */
1618 __isl_give isl_set *isl_pw_aff_non_zero_set(__isl_take isl_pw_aff *pwaff)
1619 {
1620         return pw_aff_zero_set(pwaff, 1);
1621 }
1622
1623 /* Return a set containing those elements in the shared domain
1624  * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
1625  *
1626  * We compute the difference on the shared domain and then construct
1627  * the set of values where this difference is non-negative.
1628  * If strict is set, we first subtract 1 from the difference.
1629  * If equal is set, we only return the elements where pwaff1 and pwaff2
1630  * are equal.
1631  */
1632 static __isl_give isl_set *pw_aff_gte_set(__isl_take isl_pw_aff *pwaff1,
1633         __isl_take isl_pw_aff *pwaff2, int strict, int equal)
1634 {
1635         isl_set *set1, *set2;
1636
1637         set1 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff1));
1638         set2 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff2));
1639         set1 = isl_set_intersect(set1, set2);
1640         pwaff1 = isl_pw_aff_intersect_domain(pwaff1, isl_set_copy(set1));
1641         pwaff2 = isl_pw_aff_intersect_domain(pwaff2, isl_set_copy(set1));
1642         pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_neg(pwaff2));
1643
1644         if (strict) {
1645                 isl_space *dim = isl_set_get_space(set1);
1646                 isl_aff *aff;
1647                 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
1648                 aff = isl_aff_add_constant_si(aff, -1);
1649                 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_alloc(set1, aff));
1650         } else
1651                 isl_set_free(set1);
1652
1653         if (equal)
1654                 return isl_pw_aff_zero_set(pwaff1);
1655         return isl_pw_aff_nonneg_set(pwaff1);
1656 }
1657
1658 /* Return a set containing those elements in the shared domain
1659  * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
1660  */
1661 static __isl_give isl_set *pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1662         __isl_take isl_pw_aff *pwaff2)
1663 {
1664         return pw_aff_gte_set(pwaff1, pwaff2, 0, 1);
1665 }
1666
1667 __isl_give isl_set *isl_pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1668         __isl_take isl_pw_aff *pwaff2)
1669 {
1670         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_eq_set);
1671 }
1672
1673 /* Return a set containing those elements in the shared domain
1674  * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
1675  */
1676 static __isl_give isl_set *pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1677         __isl_take isl_pw_aff *pwaff2)
1678 {
1679         return pw_aff_gte_set(pwaff1, pwaff2, 0, 0);
1680 }
1681
1682 __isl_give isl_set *isl_pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1683         __isl_take isl_pw_aff *pwaff2)
1684 {
1685         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ge_set);
1686 }
1687
1688 /* Return a set containing those elements in the shared domain
1689  * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
1690  */
1691 static __isl_give isl_set *pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1692         __isl_take isl_pw_aff *pwaff2)
1693 {
1694         return pw_aff_gte_set(pwaff1, pwaff2, 1, 0);
1695 }
1696
1697 __isl_give isl_set *isl_pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1698         __isl_take isl_pw_aff *pwaff2)
1699 {
1700         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_gt_set);
1701 }
1702
1703 __isl_give isl_set *isl_pw_aff_le_set(__isl_take isl_pw_aff *pwaff1,
1704         __isl_take isl_pw_aff *pwaff2)
1705 {
1706         return isl_pw_aff_ge_set(pwaff2, pwaff1);
1707 }
1708
1709 __isl_give isl_set *isl_pw_aff_lt_set(__isl_take isl_pw_aff *pwaff1,
1710         __isl_take isl_pw_aff *pwaff2)
1711 {
1712         return isl_pw_aff_gt_set(pwaff2, pwaff1);
1713 }
1714
1715 /* Return a set containing those elements in the shared domain
1716  * of the elements of list1 and list2 where each element in list1
1717  * has the relation specified by "fn" with each element in list2.
1718  */
1719 static __isl_give isl_set *pw_aff_list_set(__isl_take isl_pw_aff_list *list1,
1720         __isl_take isl_pw_aff_list *list2,
1721         __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1722                                     __isl_take isl_pw_aff *pwaff2))
1723 {
1724         int i, j;
1725         isl_ctx *ctx;
1726         isl_set *set;
1727
1728         if (!list1 || !list2)
1729                 goto error;
1730
1731         ctx = isl_pw_aff_list_get_ctx(list1);
1732         if (list1->n < 1 || list2->n < 1)
1733                 isl_die(ctx, isl_error_invalid,
1734                         "list should contain at least one element", goto error);
1735
1736         set = isl_set_universe(isl_pw_aff_get_domain_space(list1->p[0]));
1737         for (i = 0; i < list1->n; ++i)
1738                 for (j = 0; j < list2->n; ++j) {
1739                         isl_set *set_ij;
1740
1741                         set_ij = fn(isl_pw_aff_copy(list1->p[i]),
1742                                     isl_pw_aff_copy(list2->p[j]));
1743                         set = isl_set_intersect(set, set_ij);
1744                 }
1745
1746         isl_pw_aff_list_free(list1);
1747         isl_pw_aff_list_free(list2);
1748         return set;
1749 error:
1750         isl_pw_aff_list_free(list1);
1751         isl_pw_aff_list_free(list2);
1752         return NULL;
1753 }
1754
1755 /* Return a set containing those elements in the shared domain
1756  * of the elements of list1 and list2 where each element in list1
1757  * is equal to each element in list2.
1758  */
1759 __isl_give isl_set *isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list *list1,
1760         __isl_take isl_pw_aff_list *list2)
1761 {
1762         return pw_aff_list_set(list1, list2, &isl_pw_aff_eq_set);
1763 }
1764
1765 __isl_give isl_set *isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list *list1,
1766         __isl_take isl_pw_aff_list *list2)
1767 {
1768         return pw_aff_list_set(list1, list2, &isl_pw_aff_ne_set);
1769 }
1770
1771 /* Return a set containing those elements in the shared domain
1772  * of the elements of list1 and list2 where each element in list1
1773  * is less than or equal to each element in list2.
1774  */
1775 __isl_give isl_set *isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list *list1,
1776         __isl_take isl_pw_aff_list *list2)
1777 {
1778         return pw_aff_list_set(list1, list2, &isl_pw_aff_le_set);
1779 }
1780
1781 __isl_give isl_set *isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list *list1,
1782         __isl_take isl_pw_aff_list *list2)
1783 {
1784         return pw_aff_list_set(list1, list2, &isl_pw_aff_lt_set);
1785 }
1786
1787 __isl_give isl_set *isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list *list1,
1788         __isl_take isl_pw_aff_list *list2)
1789 {
1790         return pw_aff_list_set(list1, list2, &isl_pw_aff_ge_set);
1791 }
1792
1793 __isl_give isl_set *isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list *list1,
1794         __isl_take isl_pw_aff_list *list2)
1795 {
1796         return pw_aff_list_set(list1, list2, &isl_pw_aff_gt_set);
1797 }
1798
1799
1800 /* Return a set containing those elements in the shared domain
1801  * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
1802  */
1803 static __isl_give isl_set *pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1804         __isl_take isl_pw_aff *pwaff2)
1805 {
1806         isl_set *set_lt, *set_gt;
1807
1808         set_lt = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1),
1809                                    isl_pw_aff_copy(pwaff2));
1810         set_gt = isl_pw_aff_gt_set(pwaff1, pwaff2);
1811         return isl_set_union_disjoint(set_lt, set_gt);
1812 }
1813
1814 __isl_give isl_set *isl_pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1815         __isl_take isl_pw_aff *pwaff2)
1816 {
1817         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ne_set);
1818 }
1819
1820 __isl_give isl_pw_aff *isl_pw_aff_scale_down(__isl_take isl_pw_aff *pwaff,
1821         isl_int v)
1822 {
1823         int i;
1824
1825         if (isl_int_is_one(v))
1826                 return pwaff;
1827         if (!isl_int_is_pos(v))
1828                 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1829                         "factor needs to be positive",
1830                         return isl_pw_aff_free(pwaff));
1831         pwaff = isl_pw_aff_cow(pwaff);
1832         if (!pwaff)
1833                 return NULL;
1834         if (pwaff->n == 0)
1835                 return pwaff;
1836
1837         for (i = 0; i < pwaff->n; ++i) {
1838                 pwaff->p[i].aff = isl_aff_scale_down(pwaff->p[i].aff, v);
1839                 if (!pwaff->p[i].aff)
1840                         return isl_pw_aff_free(pwaff);
1841         }
1842
1843         return pwaff;
1844 }
1845
1846 __isl_give isl_pw_aff *isl_pw_aff_floor(__isl_take isl_pw_aff *pwaff)
1847 {
1848         int i;
1849
1850         pwaff = isl_pw_aff_cow(pwaff);
1851         if (!pwaff)
1852                 return NULL;
1853         if (pwaff->n == 0)
1854                 return pwaff;
1855
1856         for (i = 0; i < pwaff->n; ++i) {
1857                 pwaff->p[i].aff = isl_aff_floor(pwaff->p[i].aff);
1858                 if (!pwaff->p[i].aff)
1859                         return isl_pw_aff_free(pwaff);
1860         }
1861
1862         return pwaff;
1863 }
1864
1865 __isl_give isl_pw_aff *isl_pw_aff_ceil(__isl_take isl_pw_aff *pwaff)
1866 {
1867         int i;
1868
1869         pwaff = isl_pw_aff_cow(pwaff);
1870         if (!pwaff)
1871                 return NULL;
1872         if (pwaff->n == 0)
1873                 return pwaff;
1874
1875         for (i = 0; i < pwaff->n; ++i) {
1876                 pwaff->p[i].aff = isl_aff_ceil(pwaff->p[i].aff);
1877                 if (!pwaff->p[i].aff)
1878                         return isl_pw_aff_free(pwaff);
1879         }
1880
1881         return pwaff;
1882 }
1883
1884 /* Assuming that "cond1" and "cond2" are disjoint,
1885  * return an affine expression that is equal to pwaff1 on cond1
1886  * and to pwaff2 on cond2.
1887  */
1888 static __isl_give isl_pw_aff *isl_pw_aff_select(
1889         __isl_take isl_set *cond1, __isl_take isl_pw_aff *pwaff1,
1890         __isl_take isl_set *cond2, __isl_take isl_pw_aff *pwaff2)
1891 {
1892         pwaff1 = isl_pw_aff_intersect_domain(pwaff1, cond1);
1893         pwaff2 = isl_pw_aff_intersect_domain(pwaff2, cond2);
1894
1895         return isl_pw_aff_add_disjoint(pwaff1, pwaff2);
1896 }
1897
1898 /* Return an affine expression that is equal to pwaff_true for elements
1899  * where "cond" is non-zero and to pwaff_false for elements where "cond"
1900  * is zero.
1901  * That is, return cond ? pwaff_true : pwaff_false;
1902  */
1903 __isl_give isl_pw_aff *isl_pw_aff_cond(__isl_take isl_pw_aff *cond,
1904         __isl_take isl_pw_aff *pwaff_true, __isl_take isl_pw_aff *pwaff_false)
1905 {
1906         isl_set *cond_true, *cond_false;
1907
1908         cond_true = isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond));
1909         cond_false = isl_pw_aff_zero_set(cond);
1910         return isl_pw_aff_select(cond_true, pwaff_true,
1911                                  cond_false, pwaff_false);
1912 }
1913
1914 int isl_aff_is_cst(__isl_keep isl_aff *aff)
1915 {
1916         if (!aff)
1917                 return -1;
1918
1919         return isl_seq_first_non_zero(aff->v->el + 2, aff->v->size - 2) == -1;
1920 }
1921
1922 /* Check whether pwaff is a piecewise constant.
1923  */
1924 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff)
1925 {
1926         int i;
1927
1928         if (!pwaff)
1929                 return -1;
1930
1931         for (i = 0; i < pwaff->n; ++i) {
1932                 int is_cst = isl_aff_is_cst(pwaff->p[i].aff);
1933                 if (is_cst < 0 || !is_cst)
1934                         return is_cst;
1935         }
1936
1937         return 1;
1938 }
1939
1940 __isl_give isl_aff *isl_aff_mul(__isl_take isl_aff *aff1,
1941         __isl_take isl_aff *aff2)
1942 {
1943         if (!isl_aff_is_cst(aff2) && isl_aff_is_cst(aff1))
1944                 return isl_aff_mul(aff2, aff1);
1945
1946         if (!isl_aff_is_cst(aff2))
1947                 isl_die(isl_aff_get_ctx(aff1), isl_error_invalid,
1948                         "at least one affine expression should be constant",
1949                         goto error);
1950
1951         aff1 = isl_aff_cow(aff1);
1952         if (!aff1 || !aff2)
1953                 goto error;
1954
1955         aff1 = isl_aff_scale(aff1, aff2->v->el[1]);
1956         aff1 = isl_aff_scale_down(aff1, aff2->v->el[0]);
1957
1958         isl_aff_free(aff2);
1959         return aff1;
1960 error:
1961         isl_aff_free(aff1);
1962         isl_aff_free(aff2);
1963         return NULL;
1964 }
1965
1966 static __isl_give isl_pw_aff *pw_aff_add(__isl_take isl_pw_aff *pwaff1,
1967         __isl_take isl_pw_aff *pwaff2)
1968 {
1969         return isl_pw_aff_on_shared_domain(pwaff1, pwaff2, &isl_aff_add);
1970 }
1971
1972 __isl_give isl_pw_aff *isl_pw_aff_add(__isl_take isl_pw_aff *pwaff1,
1973         __isl_take isl_pw_aff *pwaff2)
1974 {
1975         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_add);
1976 }
1977
1978 __isl_give isl_pw_aff *isl_pw_aff_union_add(__isl_take isl_pw_aff *pwaff1,
1979         __isl_take isl_pw_aff *pwaff2)
1980 {
1981         return isl_pw_aff_union_add_(pwaff1, pwaff2);
1982 }
1983
1984 static __isl_give isl_pw_aff *pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
1985         __isl_take isl_pw_aff *pwaff2)
1986 {
1987         return isl_pw_aff_on_shared_domain(pwaff1, pwaff2, &isl_aff_mul);
1988 }
1989
1990 __isl_give isl_pw_aff *isl_pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
1991         __isl_take isl_pw_aff *pwaff2)
1992 {
1993         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_mul);
1994 }
1995
1996 static __isl_give isl_pw_aff *pw_aff_min(__isl_take isl_pw_aff *pwaff1,
1997         __isl_take isl_pw_aff *pwaff2)
1998 {
1999         isl_set *le;
2000         isl_set *dom;
2001
2002         dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1)),
2003                                 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2)));
2004         le = isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1),
2005                                 isl_pw_aff_copy(pwaff2));
2006         dom = isl_set_subtract(dom, isl_set_copy(le));
2007         return isl_pw_aff_select(le, pwaff1, dom, pwaff2);
2008 }
2009
2010 __isl_give isl_pw_aff *isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1,
2011         __isl_take isl_pw_aff *pwaff2)
2012 {
2013         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_min);
2014 }
2015
2016 static __isl_give isl_pw_aff *pw_aff_max(__isl_take isl_pw_aff *pwaff1,
2017         __isl_take isl_pw_aff *pwaff2)
2018 {
2019         isl_set *ge;
2020         isl_set *dom;
2021
2022         dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1)),
2023                                 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2)));
2024         ge = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1),
2025                                 isl_pw_aff_copy(pwaff2));
2026         dom = isl_set_subtract(dom, isl_set_copy(ge));
2027         return isl_pw_aff_select(ge, pwaff1, dom, pwaff2);
2028 }
2029
2030 __isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1,
2031         __isl_take isl_pw_aff *pwaff2)
2032 {
2033         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_max);
2034 }
2035
2036 static __isl_give isl_pw_aff *pw_aff_list_reduce(
2037         __isl_take isl_pw_aff_list *list,
2038         __isl_give isl_pw_aff *(*fn)(__isl_take isl_pw_aff *pwaff1,
2039                                         __isl_take isl_pw_aff *pwaff2))
2040 {
2041         int i;
2042         isl_ctx *ctx;
2043         isl_pw_aff *res;
2044
2045         if (!list)
2046                 return NULL;
2047
2048         ctx = isl_pw_aff_list_get_ctx(list);
2049         if (list->n < 1)
2050                 isl_die(ctx, isl_error_invalid,
2051                         "list should contain at least one element",
2052                         return isl_pw_aff_list_free(list));
2053
2054         res = isl_pw_aff_copy(list->p[0]);
2055         for (i = 1; i < list->n; ++i)
2056                 res = fn(res, isl_pw_aff_copy(list->p[i]));
2057
2058         isl_pw_aff_list_free(list);
2059         return res;
2060 }
2061
2062 /* Return an isl_pw_aff that maps each element in the intersection of the
2063  * domains of the elements of list to the minimal corresponding affine
2064  * expression.
2065  */
2066 __isl_give isl_pw_aff *isl_pw_aff_list_min(__isl_take isl_pw_aff_list *list)
2067 {
2068         return pw_aff_list_reduce(list, &isl_pw_aff_min);
2069 }
2070
2071 /* Return an isl_pw_aff that maps each element in the intersection of the
2072  * domains of the elements of list to the maximal corresponding affine
2073  * expression.
2074  */
2075 __isl_give isl_pw_aff *isl_pw_aff_list_max(__isl_take isl_pw_aff_list *list)
2076 {
2077         return pw_aff_list_reduce(list, &isl_pw_aff_max);
2078 }
2079
2080 #undef BASE
2081 #define BASE aff
2082
2083 #include <isl_multi_templ.c>
2084
2085 /* Construct an isl_multi_aff in the given space with value zero in
2086  * each of the output dimensions.
2087  */
2088 __isl_give isl_multi_aff *isl_multi_aff_zero(__isl_take isl_space *space)
2089 {
2090         int n;
2091         isl_multi_aff *ma;
2092
2093         if (!space)
2094                 return NULL;
2095
2096         n = isl_space_dim(space , isl_dim_out);
2097         ma = isl_multi_aff_alloc(isl_space_copy(space));
2098
2099         if (!n)
2100                 isl_space_free(space);
2101         else {
2102                 int i;
2103                 isl_local_space *ls;
2104                 isl_aff *aff;
2105
2106                 space = isl_space_domain(space);
2107                 ls = isl_local_space_from_space(space);
2108                 aff = isl_aff_zero_on_domain(ls);
2109
2110                 for (i = 0; i < n; ++i)
2111                         ma = isl_multi_aff_set_aff(ma, i, isl_aff_copy(aff));
2112
2113                 isl_aff_free(aff);
2114         }
2115
2116         return ma;
2117 }
2118
2119 /* Create an isl_pw_multi_aff with the given isl_multi_aff on a universe
2120  * domain.
2121  */
2122 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_multi_aff(
2123         __isl_take isl_multi_aff *ma)
2124 {
2125         isl_set *dom = isl_set_universe(isl_multi_aff_get_domain_space(ma));
2126         return isl_pw_multi_aff_alloc(dom, ma);
2127 }
2128
2129 __isl_give isl_multi_aff *isl_multi_aff_add(__isl_take isl_multi_aff *maff1,
2130         __isl_take isl_multi_aff *maff2)
2131 {
2132         int i;
2133         isl_ctx *ctx;
2134
2135         maff1 = isl_multi_aff_cow(maff1);
2136         if (!maff1 || !maff2)
2137                 goto error;
2138
2139         ctx = isl_multi_aff_get_ctx(maff1);
2140         if (!isl_space_is_equal(maff1->space, maff2->space))
2141                 isl_die(ctx, isl_error_invalid,
2142                         "spaces don't match", goto error);
2143
2144         for (i = 0; i < maff1->n; ++i) {
2145                 maff1->p[i] = isl_aff_add(maff1->p[i],
2146                                             isl_aff_copy(maff2->p[i]));
2147                 if (!maff1->p[i])
2148                         goto error;
2149         }
2150
2151         isl_multi_aff_free(maff2);
2152         return maff1;
2153 error:
2154         isl_multi_aff_free(maff1);
2155         isl_multi_aff_free(maff2);
2156         return NULL;
2157 }
2158
2159 /* Exploit the equalities in "eq" to simplify the affine expressions.
2160  */
2161 static __isl_give isl_multi_aff *isl_multi_aff_substitute_equalities(
2162         __isl_take isl_multi_aff *maff, __isl_take isl_basic_set *eq)
2163 {
2164         int i;
2165
2166         maff = isl_multi_aff_cow(maff);
2167         if (!maff || !eq)
2168                 goto error;
2169
2170         for (i = 0; i < maff->n; ++i) {
2171                 maff->p[i] = isl_aff_substitute_equalities(maff->p[i],
2172                                                     isl_basic_set_copy(eq));
2173                 if (!maff->p[i])
2174                         goto error;
2175         }
2176
2177         isl_basic_set_free(eq);
2178         return maff;
2179 error:
2180         isl_basic_set_free(eq);
2181         isl_multi_aff_free(maff);
2182         return NULL;
2183 }
2184
2185 __isl_give isl_multi_aff *isl_multi_aff_scale(__isl_take isl_multi_aff *maff,
2186         isl_int f)
2187 {
2188         int i;
2189
2190         maff = isl_multi_aff_cow(maff);
2191         if (!maff)
2192                 return NULL;
2193
2194         for (i = 0; i < maff->n; ++i) {
2195                 maff->p[i] = isl_aff_scale(maff->p[i], f);
2196                 if (!maff->p[i])
2197                         return isl_multi_aff_free(maff);
2198         }
2199
2200         return maff;
2201 }
2202
2203 __isl_give isl_multi_aff *isl_multi_aff_add_on_domain(__isl_keep isl_set *dom,
2204         __isl_take isl_multi_aff *maff1, __isl_take isl_multi_aff *maff2)
2205 {
2206         maff1 = isl_multi_aff_add(maff1, maff2);
2207         maff1 = isl_multi_aff_gist(maff1, isl_set_copy(dom));
2208         return maff1;
2209 }
2210
2211 int isl_multi_aff_is_empty(__isl_keep isl_multi_aff *maff)
2212 {
2213         if (!maff)
2214                 return -1;
2215
2216         return 0;
2217 }
2218
2219 int isl_multi_aff_plain_is_equal(__isl_keep isl_multi_aff *maff1,
2220         __isl_keep isl_multi_aff *maff2)
2221 {
2222         int i;
2223         int equal;
2224
2225         if (!maff1 || !maff2)
2226                 return -1;
2227         if (maff1->n != maff2->n)
2228                 return 0;
2229         equal = isl_space_is_equal(maff1->space, maff2->space);
2230         if (equal < 0 || !equal)
2231                 return equal;
2232
2233         for (i = 0; i < maff1->n; ++i) {
2234                 equal = isl_aff_plain_is_equal(maff1->p[i], maff2->p[i]);
2235                 if (equal < 0 || !equal)
2236                         return equal;
2237         }
2238
2239         return 1;
2240 }
2241
2242 __isl_give isl_multi_aff *isl_multi_aff_set_dim_name(
2243         __isl_take isl_multi_aff *maff,
2244         enum isl_dim_type type, unsigned pos, const char *s)
2245 {
2246         int i;
2247
2248         maff = isl_multi_aff_cow(maff);
2249         if (!maff)
2250                 return NULL;
2251
2252         maff->space = isl_space_set_dim_name(maff->space, type, pos, s);
2253         if (!maff->space)
2254                 return isl_multi_aff_free(maff);
2255         for (i = 0; i < maff->n; ++i) {
2256                 maff->p[i] = isl_aff_set_dim_name(maff->p[i], type, pos, s);
2257                 if (!maff->p[i])
2258                         return isl_multi_aff_free(maff);
2259         }
2260
2261         return maff;
2262 }
2263
2264 __isl_give isl_multi_aff *isl_multi_aff_drop_dims(__isl_take isl_multi_aff *maff,
2265         enum isl_dim_type type, unsigned first, unsigned n)
2266 {
2267         int i;
2268
2269         maff = isl_multi_aff_cow(maff);
2270         if (!maff)
2271                 return NULL;
2272
2273         maff->space = isl_space_drop_dims(maff->space, type, first, n);
2274         if (!maff->space)
2275                 return isl_multi_aff_free(maff);
2276
2277         if (type == isl_dim_out) {
2278                 for (i = 0; i < n; ++i)
2279                         isl_aff_free(maff->p[first + i]);
2280                 for (i = first; i + n < maff->n; ++i)
2281                         maff->p[i] = maff->p[i + n];
2282                 maff->n -= n;
2283                 return maff;
2284         }
2285
2286         for (i = 0; i < maff->n; ++i) {
2287                 maff->p[i] = isl_aff_drop_dims(maff->p[i], type, first, n);
2288                 if (!maff->p[i])
2289                         return isl_multi_aff_free(maff);
2290         }
2291
2292         return maff;
2293 }
2294
2295 #undef PW
2296 #define PW isl_pw_multi_aff
2297 #undef EL
2298 #define EL isl_multi_aff
2299 #undef EL_IS_ZERO
2300 #define EL_IS_ZERO is_empty
2301 #undef ZERO
2302 #define ZERO empty
2303 #undef IS_ZERO
2304 #define IS_ZERO is_empty
2305 #undef FIELD
2306 #define FIELD maff
2307 #undef DEFAULT_IS_ZERO
2308 #define DEFAULT_IS_ZERO 0
2309
2310 #define NO_NEG
2311 #define NO_EVAL
2312 #define NO_OPT
2313 #define NO_INVOLVES_DIMS
2314 #define NO_MOVE_DIMS
2315 #define NO_INSERT_DIMS
2316 #define NO_LIFT
2317 #define NO_MORPH
2318
2319 #include <isl_pw_templ.c>
2320
2321 #undef UNION
2322 #define UNION isl_union_pw_multi_aff
2323 #undef PART
2324 #define PART isl_pw_multi_aff
2325 #undef PARTS
2326 #define PARTS pw_multi_aff
2327 #define ALIGN_DOMAIN
2328
2329 #define NO_EVAL
2330
2331 #include <isl_union_templ.c>
2332
2333 static __isl_give isl_pw_multi_aff *pw_multi_aff_add(
2334         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
2335 {
2336         return isl_pw_multi_aff_on_shared_domain(pma1, pma2,
2337                                                 &isl_multi_aff_add);
2338 }
2339
2340 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_add(
2341         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
2342 {
2343         return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
2344                                                 &pw_multi_aff_add);
2345 }
2346
2347 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_add(
2348         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
2349 {
2350         return isl_pw_multi_aff_union_add_(pma1, pma2);
2351 }
2352
2353 /* Construct a map mapping the domain of the piecewise multi-affine expression
2354  * to its range, with each dimension in the range equated to the
2355  * corresponding affine expression on its cell.
2356  */
2357 __isl_give isl_map *isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
2358 {
2359         int i;
2360         isl_map *map;
2361
2362         if (!pma)
2363                 return NULL;
2364
2365         map = isl_map_empty(isl_pw_multi_aff_get_space(pma));
2366
2367         for (i = 0; i < pma->n; ++i) {
2368                 isl_multi_aff *maff;
2369                 isl_basic_map *bmap;
2370                 isl_map *map_i;
2371
2372                 maff = isl_multi_aff_copy(pma->p[i].maff);
2373                 bmap = isl_basic_map_from_multi_aff(maff);
2374                 map_i = isl_map_from_basic_map(bmap);
2375                 map_i = isl_map_intersect_domain(map_i,
2376                                                 isl_set_copy(pma->p[i].set));
2377                 map = isl_map_union_disjoint(map, map_i);
2378         }
2379
2380         isl_pw_multi_aff_free(pma);
2381         return map;
2382 }
2383
2384 __isl_give isl_set *isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
2385 {
2386         if (!isl_space_is_set(pma->dim))
2387                 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
2388                         "isl_pw_multi_aff cannot be converted into an isl_set",
2389                         return isl_pw_multi_aff_free(pma));
2390
2391         return isl_map_from_pw_multi_aff(pma);
2392 }
2393
2394 /* Given a basic map with a single output dimension that is defined
2395  * in terms of the parameters and input dimensions using an equality,
2396  * extract an isl_aff that expresses the output dimension in terms
2397  * of the parameters and input dimensions.
2398  *
2399  * Since some applications expect the result of isl_pw_multi_aff_from_map
2400  * to only contain integer affine expressions, we compute the floor
2401  * of the expression before returning.
2402  *
2403  * This function shares some similarities with
2404  * isl_basic_map_has_defining_equality and isl_constraint_get_bound.
2405  */
2406 static __isl_give isl_aff *extract_isl_aff_from_basic_map(
2407         __isl_take isl_basic_map *bmap)
2408 {
2409         int i;
2410         unsigned offset;
2411         unsigned total;
2412         isl_local_space *ls;
2413         isl_aff *aff;
2414
2415         if (!bmap)
2416                 return NULL;
2417         if (isl_basic_map_dim(bmap, isl_dim_out) != 1)
2418                 isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
2419                         "basic map should have a single output dimension",
2420                         goto error);
2421         offset = isl_basic_map_offset(bmap, isl_dim_out);
2422         total = isl_basic_map_total_dim(bmap);
2423         for (i = 0; i < bmap->n_eq; ++i) {
2424                 if (isl_int_is_zero(bmap->eq[i][offset]))
2425                         continue;
2426                 if (isl_seq_first_non_zero(bmap->eq[i] + offset + 1,
2427                                            1 + total - (offset + 1)) != -1)
2428                         continue;
2429                 break;
2430         }
2431         if (i >= bmap->n_eq)
2432                 isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
2433                         "unable to find suitable equality", goto error);
2434         ls = isl_basic_map_get_local_space(bmap);
2435         aff = isl_aff_alloc(isl_local_space_domain(ls));
2436         if (!aff)
2437                 goto error;
2438         if (isl_int_is_neg(bmap->eq[i][offset]))
2439                 isl_seq_cpy(aff->v->el + 1, bmap->eq[i], offset);
2440         else
2441                 isl_seq_neg(aff->v->el + 1, bmap->eq[i], offset);
2442         isl_seq_clr(aff->v->el + 1 + offset, aff->v->size - (1 + offset));
2443         isl_int_abs(aff->v->el[0], bmap->eq[i][offset]);
2444         isl_basic_map_free(bmap);
2445
2446         aff = isl_aff_remove_unused_divs(aff);
2447         aff = isl_aff_floor(aff);
2448         return aff;
2449 error:
2450         isl_basic_map_free(bmap);
2451         return NULL;
2452 }
2453
2454 /* Given a basic map where each output dimension is defined
2455  * in terms of the parameters and input dimensions using an equality,
2456  * extract an isl_multi_aff that expresses the output dimensions in terms
2457  * of the parameters and input dimensions.
2458  */
2459 static __isl_give isl_multi_aff *extract_isl_multi_aff_from_basic_map(
2460         __isl_take isl_basic_map *bmap)
2461 {
2462         int i;
2463         unsigned n_out;
2464         isl_multi_aff *ma;
2465
2466         if (!bmap)
2467                 return NULL;
2468
2469         ma = isl_multi_aff_alloc(isl_basic_map_get_space(bmap));
2470         n_out = isl_basic_map_dim(bmap, isl_dim_out);
2471
2472         for (i = 0; i < n_out; ++i) {
2473                 isl_basic_map *bmap_i;
2474                 isl_aff *aff;
2475
2476                 bmap_i = isl_basic_map_copy(bmap);
2477                 bmap_i = isl_basic_map_project_out(bmap_i, isl_dim_out,
2478                                                         i + 1, n_out - (1 + i));
2479                 bmap_i = isl_basic_map_project_out(bmap_i, isl_dim_out, 0, i);
2480                 aff = extract_isl_aff_from_basic_map(bmap_i);
2481                 ma = isl_multi_aff_set_aff(ma, i, aff);
2482         }
2483
2484         isl_basic_map_free(bmap);
2485
2486         return ma;
2487 }
2488
2489 /* Create an isl_pw_multi_aff that is equivalent to
2490  * isl_map_intersect_domain(isl_map_from_basic_map(bmap), domain).
2491  * The given basic map is such that each output dimension is defined
2492  * in terms of the parameters and input dimensions using an equality.
2493  */
2494 static __isl_give isl_pw_multi_aff *plain_pw_multi_aff_from_map(
2495         __isl_take isl_set *domain, __isl_take isl_basic_map *bmap)
2496 {
2497         isl_multi_aff *ma;
2498
2499         ma = extract_isl_multi_aff_from_basic_map(bmap);
2500         return isl_pw_multi_aff_alloc(domain, ma);
2501 }
2502
2503 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
2504  * This obivously only works if the input "map" is single-valued.
2505  * If so, we compute the lexicographic minimum of the image in the form
2506  * of an isl_pw_multi_aff.  Since the image is unique, it is equal
2507  * to its lexicographic minimum.
2508  * If the input is not single-valued, we produce an error.
2509  *
2510  * As a special case, we first check if all output dimensions are uniquely
2511  * defined in terms of the parameters and input dimensions over the entire
2512  * domain.  If so, we extract the desired isl_pw_multi_aff directly
2513  * from the affine hull of "map" and its domain.
2514  */
2515 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_map(__isl_take isl_map *map)
2516 {
2517         int i;
2518         int sv;
2519         isl_pw_multi_aff *pma;
2520         isl_basic_map *hull;
2521
2522         if (!map)
2523                 return NULL;
2524
2525         hull = isl_map_affine_hull(isl_map_copy(map));
2526         sv = isl_basic_map_plain_is_single_valued(hull);
2527         if (sv >= 0 && sv)
2528                 return plain_pw_multi_aff_from_map(isl_map_domain(map), hull);
2529         isl_basic_map_free(hull);
2530         if (sv < 0)
2531                 goto error;
2532
2533         sv = isl_map_is_single_valued(map);
2534         if (sv < 0)
2535                 goto error;
2536         if (!sv)
2537                 isl_die(isl_map_get_ctx(map), isl_error_invalid,
2538                         "map is not single-valued", goto error);
2539         map = isl_map_make_disjoint(map);
2540         if (!map)
2541                 return NULL;
2542
2543         pma = isl_pw_multi_aff_empty(isl_map_get_space(map));
2544
2545         for (i = 0; i < map->n; ++i) {
2546                 isl_pw_multi_aff *pma_i;
2547                 isl_basic_map *bmap;
2548                 bmap = isl_basic_map_copy(map->p[i]);
2549                 pma_i = isl_basic_map_lexmin_pw_multi_aff(bmap);
2550                 pma = isl_pw_multi_aff_add_disjoint(pma, pma_i);
2551         }
2552
2553         isl_map_free(map);
2554         return pma;
2555 error:
2556         isl_map_free(map);
2557         return NULL;
2558 }
2559
2560 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_set(__isl_take isl_set *set)
2561 {
2562         return isl_pw_multi_aff_from_map(set);
2563 }
2564
2565 /* Return the piecewise affine expression "set ? 1 : 0".
2566  */
2567 __isl_give isl_pw_aff *isl_set_indicator_function(__isl_take isl_set *set)
2568 {
2569         isl_pw_aff *pa;
2570         isl_space *space = isl_set_get_space(set);
2571         isl_local_space *ls = isl_local_space_from_space(space);
2572         isl_aff *zero = isl_aff_zero_on_domain(isl_local_space_copy(ls));
2573         isl_aff *one = isl_aff_zero_on_domain(ls);
2574
2575         one = isl_aff_add_constant_si(one, 1);
2576         pa = isl_pw_aff_alloc(isl_set_copy(set), one);
2577         set = isl_set_complement(set);
2578         pa = isl_pw_aff_add_disjoint(pa, isl_pw_aff_alloc(set, zero));
2579
2580         return pa;
2581 }
2582
2583 /* Plug in "subs" for dimension "type", "pos" of "aff".
2584  *
2585  * Let i be the dimension to replace and let "subs" be of the form
2586  *
2587  *      f/d
2588  *
2589  * and "aff" of the form
2590  *
2591  *      (a i + g)/m
2592  *
2593  * The result is
2594  *
2595  *      floor((a f + d g')/(m d))
2596  *
2597  * where g' is the result of plugging in "subs" in each of the integer
2598  * divisions in g.
2599  */
2600 __isl_give isl_aff *isl_aff_substitute(__isl_take isl_aff *aff,
2601         enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs)
2602 {
2603         isl_ctx *ctx;
2604         isl_int v;
2605
2606         aff = isl_aff_cow(aff);
2607         if (!aff || !subs)
2608                 return isl_aff_free(aff);
2609
2610         ctx = isl_aff_get_ctx(aff);
2611         if (!isl_space_is_equal(aff->ls->dim, subs->ls->dim))
2612                 isl_die(ctx, isl_error_invalid,
2613                         "spaces don't match", return isl_aff_free(aff));
2614         if (isl_local_space_dim(subs->ls, isl_dim_div) != 0)
2615                 isl_die(ctx, isl_error_unsupported,
2616                         "cannot handle divs yet", return isl_aff_free(aff));
2617
2618         aff->ls = isl_local_space_substitute(aff->ls, type, pos, subs);
2619         if (!aff->ls)
2620                 return isl_aff_free(aff);
2621
2622         aff->v = isl_vec_cow(aff->v);
2623         if (!aff->v)
2624                 return isl_aff_free(aff);
2625
2626         pos += isl_local_space_offset(aff->ls, type);
2627
2628         isl_int_init(v);
2629         isl_int_set(v, aff->v->el[1 + pos]);
2630         isl_int_set_si(aff->v->el[1 + pos], 0);
2631         isl_seq_combine(aff->v->el + 1, subs->v->el[0], aff->v->el + 1,
2632                         v, subs->v->el + 1, subs->v->size - 1);
2633         isl_int_mul(aff->v->el[0], aff->v->el[0], subs->v->el[0]);
2634         isl_int_clear(v);
2635
2636         return aff;
2637 }
2638
2639 /* Plug in "subs" for dimension "type", "pos" in each of the affine
2640  * expressions in "maff".
2641  */
2642 __isl_give isl_multi_aff *isl_multi_aff_substitute(
2643         __isl_take isl_multi_aff *maff, enum isl_dim_type type, unsigned pos,
2644         __isl_keep isl_aff *subs)
2645 {
2646         int i;
2647
2648         maff = isl_multi_aff_cow(maff);
2649         if (!maff || !subs)
2650                 return isl_multi_aff_free(maff);
2651
2652         if (type == isl_dim_in)
2653                 type = isl_dim_set;
2654
2655         for (i = 0; i < maff->n; ++i) {
2656                 maff->p[i] = isl_aff_substitute(maff->p[i], type, pos, subs);
2657                 if (!maff->p[i])
2658                         return isl_multi_aff_free(maff);
2659         }
2660
2661         return maff;
2662 }
2663
2664 /* Plug in "subs" for dimension "type", "pos" of "pma".
2665  *
2666  * pma is of the form
2667  *
2668  *      A_i(v) -> M_i(v)
2669  *
2670  * while subs is of the form
2671  *
2672  *      v' = B_j(v) -> S_j
2673  *
2674  * Each pair i,j such that C_ij = A_i \cap B_i is non-empty
2675  * has a contribution in the result, in particular
2676  *
2677  *      C_ij(S_j) -> M_i(S_j)
2678  *
2679  * Note that plugging in S_j in C_ij may also result in an empty set
2680  * and this contribution should simply be discarded.
2681  */
2682 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_substitute(
2683         __isl_take isl_pw_multi_aff *pma, enum isl_dim_type type, unsigned pos,
2684         __isl_keep isl_pw_aff *subs)
2685 {
2686         int i, j, n;
2687         isl_pw_multi_aff *res;
2688
2689         if (!pma || !subs)
2690                 return isl_pw_multi_aff_free(pma);
2691
2692         n = pma->n * subs->n;
2693         res = isl_pw_multi_aff_alloc_size(isl_space_copy(pma->dim), n);
2694
2695         for (i = 0; i < pma->n; ++i) {
2696                 for (j = 0; j < subs->n; ++j) {
2697                         isl_set *common;
2698                         isl_multi_aff *res_ij;
2699                         common = isl_set_intersect(
2700                                         isl_set_copy(pma->p[i].set),
2701                                         isl_set_copy(subs->p[j].set));
2702                         common = isl_set_substitute(common,
2703                                         type, pos, subs->p[j].aff);
2704                         if (isl_set_plain_is_empty(common)) {
2705                                 isl_set_free(common);
2706                                 continue;
2707                         }
2708
2709                         res_ij = isl_multi_aff_substitute(
2710                                         isl_multi_aff_copy(pma->p[i].maff),
2711                                         type, pos, subs->p[j].aff);
2712
2713                         res = isl_pw_multi_aff_add_piece(res, common, res_ij);
2714                 }
2715         }
2716
2717         isl_pw_multi_aff_free(pma);
2718         return res;
2719 }
2720
2721 /* Extend the local space of "dst" to include the divs
2722  * in the local space of "src".
2723  */
2724 __isl_give isl_aff *isl_aff_align_divs(__isl_take isl_aff *dst,
2725         __isl_keep isl_aff *src)
2726 {
2727         isl_ctx *ctx;
2728         int *exp1 = NULL;
2729         int *exp2 = NULL;
2730         isl_mat *div;
2731
2732         if (!src || !dst)
2733                 return isl_aff_free(dst);
2734
2735         ctx = isl_aff_get_ctx(src);
2736         if (!isl_space_is_equal(src->ls->dim, dst->ls->dim))
2737                 isl_die(ctx, isl_error_invalid,
2738                         "spaces don't match", goto error);
2739
2740         if (src->ls->div->n_row == 0)
2741                 return dst;
2742
2743         exp1 = isl_alloc_array(ctx, int, src->ls->div->n_row);
2744         exp2 = isl_alloc_array(ctx, int, dst->ls->div->n_row);
2745         if (!exp1 || !exp2)
2746                 goto error;
2747
2748         div = isl_merge_divs(src->ls->div, dst->ls->div, exp1, exp2);
2749         dst = isl_aff_expand_divs(dst, div, exp2);
2750         free(exp1);
2751         free(exp2);
2752
2753         return dst;
2754 error:
2755         free(exp1);
2756         free(exp2);
2757         return isl_aff_free(dst);
2758 }
2759
2760 /* Adjust the local spaces of the affine expressions in "maff"
2761  * such that they all have the save divs.
2762  */
2763 __isl_give isl_multi_aff *isl_multi_aff_align_divs(
2764         __isl_take isl_multi_aff *maff)
2765 {
2766         int i;
2767
2768         if (!maff)
2769                 return NULL;
2770         if (maff->n == 0)
2771                 return maff;
2772         maff = isl_multi_aff_cow(maff);
2773         if (!maff)
2774                 return NULL;
2775
2776         for (i = 1; i < maff->n; ++i)
2777                 maff->p[0] = isl_aff_align_divs(maff->p[0], maff->p[i]);
2778         for (i = 1; i < maff->n; ++i) {
2779                 maff->p[i] = isl_aff_align_divs(maff->p[i], maff->p[0]);
2780                 if (!maff->p[i])
2781                         return isl_multi_aff_free(maff);
2782         }
2783
2784         return maff;
2785 }
2786
2787 __isl_give isl_aff *isl_aff_lift(__isl_take isl_aff *aff)
2788 {
2789         aff = isl_aff_cow(aff);
2790         if (!aff)
2791                 return NULL;
2792
2793         aff->ls = isl_local_space_lift(aff->ls);
2794         if (!aff->ls)
2795                 return isl_aff_free(aff);
2796
2797         return aff;
2798 }
2799
2800 /* Lift "maff" to a space with extra dimensions such that the result
2801  * has no more existentially quantified variables.
2802  * If "ls" is not NULL, then *ls is assigned the local space that lies
2803  * at the basis of the lifting applied to "maff".
2804  */
2805 __isl_give isl_multi_aff *isl_multi_aff_lift(__isl_take isl_multi_aff *maff,
2806         __isl_give isl_local_space **ls)
2807 {
2808         int i;
2809         isl_space *space;
2810         unsigned n_div;
2811
2812         if (ls)
2813                 *ls = NULL;
2814
2815         if (!maff)
2816                 return NULL;
2817
2818         if (maff->n == 0) {
2819                 if (ls) {
2820                         isl_space *space = isl_multi_aff_get_domain_space(maff);
2821                         *ls = isl_local_space_from_space(space);
2822                         if (!*ls)
2823                                 return isl_multi_aff_free(maff);
2824                 }
2825                 return maff;
2826         }
2827
2828         maff = isl_multi_aff_cow(maff);
2829         maff = isl_multi_aff_align_divs(maff);
2830         if (!maff)
2831                 return NULL;
2832
2833         n_div = isl_aff_dim(maff->p[0], isl_dim_div);
2834         space = isl_multi_aff_get_space(maff);
2835         space = isl_space_lift(isl_space_domain(space), n_div);
2836         space = isl_space_extend_domain_with_range(space,
2837                                                 isl_multi_aff_get_space(maff));
2838         if (!space)
2839                 return isl_multi_aff_free(maff);
2840         isl_space_free(maff->space);
2841         maff->space = space;
2842
2843         if (ls) {
2844                 *ls = isl_aff_get_domain_local_space(maff->p[0]);
2845                 if (!*ls)
2846                         return isl_multi_aff_free(maff);
2847         }
2848
2849         for (i = 0; i < maff->n; ++i) {
2850                 maff->p[i] = isl_aff_lift(maff->p[i]);
2851                 if (!maff->p[i])
2852                         goto error;
2853         }
2854
2855         return maff;
2856 error:
2857         if (ls)
2858                 isl_local_space_free(*ls);
2859         return isl_multi_aff_free(maff);
2860 }
2861
2862
2863 /* Extract an isl_pw_aff corresponding to output dimension "pos" of "pma".
2864  */
2865 __isl_give isl_pw_aff *isl_pw_multi_aff_get_pw_aff(
2866         __isl_keep isl_pw_multi_aff *pma, int pos)
2867 {
2868         int i;
2869         int n_out;
2870         isl_space *space;
2871         isl_pw_aff *pa;
2872
2873         if (!pma)
2874                 return NULL;
2875
2876         n_out = isl_pw_multi_aff_dim(pma, isl_dim_out);
2877         if (pos < 0 || pos >= n_out)
2878                 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
2879                         "index out of bounds", return NULL);
2880
2881         space = isl_pw_multi_aff_get_space(pma);
2882         space = isl_space_drop_dims(space, isl_dim_out,
2883                                     pos + 1, n_out - pos - 1);
2884         space = isl_space_drop_dims(space, isl_dim_out, 0, pos);
2885
2886         pa = isl_pw_aff_alloc_size(space, pma->n);
2887         for (i = 0; i < pma->n; ++i) {
2888                 isl_aff *aff;
2889                 aff = isl_multi_aff_get_aff(pma->p[i].maff, pos);
2890                 pa = isl_pw_aff_add_piece(pa, isl_set_copy(pma->p[i].set), aff);
2891         }
2892
2893         return pa;
2894 }
2895
2896 /* Return an isl_pw_multi_aff with the given "set" as domain and
2897  * an unnamed zero-dimensional range.
2898  */
2899 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_domain(
2900         __isl_take isl_set *set)
2901 {
2902         isl_multi_aff *ma;
2903         isl_space *space;
2904
2905         space = isl_set_get_space(set);
2906         space = isl_space_from_domain(space);
2907         ma = isl_multi_aff_zero(space);
2908         return isl_pw_multi_aff_alloc(set, ma);
2909 }
2910
2911 /* Add an isl_pw_multi_aff with the given "set" as domain and
2912  * an unnamed zero-dimensional range to *user.
2913  */
2914 static int add_pw_multi_aff_from_domain(__isl_take isl_set *set, void *user)
2915 {
2916         isl_union_pw_multi_aff **upma = user;
2917         isl_pw_multi_aff *pma;
2918
2919         pma = isl_pw_multi_aff_from_domain(set);
2920         *upma = isl_union_pw_multi_aff_add_pw_multi_aff(*upma, pma);
2921
2922         return 0;
2923 }
2924
2925 /* Return an isl_union_pw_multi_aff with the given "uset" as domain and
2926  * an unnamed zero-dimensional range.
2927  */
2928 __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_from_domain(
2929         __isl_take isl_union_set *uset)
2930 {
2931         isl_space *space;
2932         isl_union_pw_multi_aff *upma;
2933
2934         if (!uset)
2935                 return NULL;
2936
2937         space = isl_union_set_get_space(uset);
2938         upma = isl_union_pw_multi_aff_empty(space);
2939
2940         if (isl_union_set_foreach_set(uset,
2941                                     &add_pw_multi_aff_from_domain, &upma) < 0)
2942                 goto error;
2943
2944         isl_union_set_free(uset);
2945         return upma;
2946 error:
2947         isl_union_set_free(uset);
2948         isl_union_pw_multi_aff_free(upma);
2949         return NULL;
2950 }
2951
2952 /* Convert "pma" to an isl_map and add it to *umap.
2953  */
2954 static int map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma, void *user)
2955 {
2956         isl_union_map **umap = user;
2957         isl_map *map;
2958
2959         map = isl_map_from_pw_multi_aff(pma);
2960         *umap = isl_union_map_add_map(*umap, map);
2961
2962         return 0;
2963 }
2964
2965 /* Construct a union map mapping the domain of the union
2966  * piecewise multi-affine expression to its range, with each dimension
2967  * in the range equated to the corresponding affine expression on its cell.
2968  */
2969 __isl_give isl_union_map *isl_union_map_from_union_pw_multi_aff(
2970         __isl_take isl_union_pw_multi_aff *upma)
2971 {
2972         isl_space *space;
2973         isl_union_map *umap;
2974
2975         if (!upma)
2976                 return NULL;
2977
2978         space = isl_union_pw_multi_aff_get_space(upma);
2979         umap = isl_union_map_empty(space);
2980
2981         if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma,
2982                                         &map_from_pw_multi_aff, &umap) < 0)
2983                 goto error;
2984
2985         isl_union_pw_multi_aff_free(upma);
2986         return umap;
2987 error:
2988         isl_union_pw_multi_aff_free(upma);
2989         isl_union_map_free(umap);
2990         return NULL;
2991 }
2992
2993 /* Local data for bin_entry and the callback "fn".
2994  */
2995 struct isl_union_pw_multi_aff_bin_data {
2996         isl_union_pw_multi_aff *upma2;
2997         isl_union_pw_multi_aff *res;
2998         isl_pw_multi_aff *pma;
2999         int (*fn)(void **entry, void *user);
3000 };
3001
3002 /* Given an isl_pw_multi_aff from upma1, store it in data->pma
3003  * and call data->fn for each isl_pw_multi_aff in data->upma2.
3004  */
3005 static int bin_entry(void **entry, void *user)
3006 {
3007         struct isl_union_pw_multi_aff_bin_data *data = user;
3008         isl_pw_multi_aff *pma = *entry;
3009
3010         data->pma = pma;
3011         if (isl_hash_table_foreach(data->upma2->dim->ctx, &data->upma2->table,
3012                                    data->fn, data) < 0)
3013                 return -1;
3014
3015         return 0;
3016 }
3017
3018 /* Call "fn" on each pair of isl_pw_multi_affs in "upma1" and "upma2".
3019  * The isl_pw_multi_aff from upma1 is stored in data->pma (where data is
3020  * passed as user field) and the isl_pw_multi_aff from upma2 is available
3021  * as *entry.  The callback should adjust data->res if desired.
3022  */
3023 static __isl_give isl_union_pw_multi_aff *bin_op(
3024         __isl_take isl_union_pw_multi_aff *upma1,
3025         __isl_take isl_union_pw_multi_aff *upma2,
3026         int (*fn)(void **entry, void *user))
3027 {
3028         isl_space *space;
3029         struct isl_union_pw_multi_aff_bin_data data = { NULL, NULL, NULL, fn };
3030
3031         space = isl_union_pw_multi_aff_get_space(upma2);
3032         upma1 = isl_union_pw_multi_aff_align_params(upma1, space);
3033         space = isl_union_pw_multi_aff_get_space(upma1);
3034         upma2 = isl_union_pw_multi_aff_align_params(upma2, space);
3035
3036         if (!upma1 || !upma2)
3037                 goto error;
3038
3039         data.upma2 = upma2;
3040         data.res = isl_union_pw_multi_aff_alloc(isl_space_copy(upma1->dim),
3041                                        upma1->table.n);
3042         if (isl_hash_table_foreach(upma1->dim->ctx, &upma1->table,
3043                                    &bin_entry, &data) < 0)
3044                 goto error;
3045
3046         isl_union_pw_multi_aff_free(upma1);
3047         isl_union_pw_multi_aff_free(upma2);
3048         return data.res;
3049 error:
3050         isl_union_pw_multi_aff_free(upma1);
3051         isl_union_pw_multi_aff_free(upma2);
3052         isl_union_pw_multi_aff_free(data.res);
3053         return NULL;
3054 }
3055
3056 /* Given two isl_multi_affs A -> B and C -> D,
3057  * construct an isl_multi_aff (A * C) -> (B, D).
3058  */
3059 __isl_give isl_multi_aff *isl_multi_aff_flat_range_product(
3060         __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2)
3061 {
3062         int i, n1, n2;
3063         isl_aff *aff;
3064         isl_space *space;
3065         isl_multi_aff *res;
3066
3067         if (!ma1 || !ma2)
3068                 goto error;
3069
3070         space = isl_space_range_product(isl_multi_aff_get_space(ma1),
3071                                         isl_multi_aff_get_space(ma2));
3072         space = isl_space_flatten_range(space);
3073         res = isl_multi_aff_alloc(space);
3074
3075         n1 = isl_multi_aff_dim(ma1, isl_dim_out);
3076         n2 = isl_multi_aff_dim(ma2, isl_dim_out);
3077
3078         for (i = 0; i < n1; ++i) {
3079                 aff = isl_multi_aff_get_aff(ma1, i);
3080                 res = isl_multi_aff_set_aff(res, i, aff);
3081         }
3082
3083         for (i = 0; i < n2; ++i) {
3084                 aff = isl_multi_aff_get_aff(ma2, i);
3085                 res = isl_multi_aff_set_aff(res, n1 + i, aff);
3086         }
3087
3088         isl_multi_aff_free(ma1);
3089         isl_multi_aff_free(ma2);
3090         return res;
3091 error:
3092         isl_multi_aff_free(ma1);
3093         isl_multi_aff_free(ma2);
3094         return NULL;
3095 }
3096
3097 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
3098  * construct an isl_pw_multi_aff (A * C) -> (B, D).
3099  */
3100 static __isl_give isl_pw_multi_aff *pw_multi_aff_flat_range_product(
3101         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
3102 {
3103         isl_space *space;
3104
3105         space = isl_space_range_product(isl_pw_multi_aff_get_space(pma1),
3106                                         isl_pw_multi_aff_get_space(pma2));
3107         space = isl_space_flatten_range(space);
3108         return isl_pw_multi_aff_on_shared_domain_in(pma1, pma2, space,
3109                                             &isl_multi_aff_flat_range_product);
3110 }
3111
3112 /* Given two isl_pw_multi_affs A -> B and C -> D,
3113  * construct an isl_pw_multi_aff (A * C) -> (B, D).
3114  */
3115 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_flat_range_product(
3116         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
3117 {
3118         return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
3119                                             &pw_multi_aff_flat_range_product);
3120 }
3121
3122 /* If data->pma and *entry have the same domain space, then compute
3123  * their flat range product and the result to data->res.
3124  */
3125 static int flat_range_product_entry(void **entry, void *user)
3126 {
3127         struct isl_union_pw_multi_aff_bin_data *data = user;
3128         isl_pw_multi_aff *pma2 = *entry;
3129
3130         if (!isl_space_tuple_match(data->pma->dim, isl_dim_in,
3131                                  pma2->dim, isl_dim_in))
3132                 return 0;
3133
3134         pma2 = isl_pw_multi_aff_flat_range_product(
3135                                         isl_pw_multi_aff_copy(data->pma),
3136                                         isl_pw_multi_aff_copy(pma2));
3137
3138         data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res, pma2);
3139
3140         return 0;
3141 }
3142
3143 /* Given two isl_union_pw_multi_affs A -> B and C -> D,
3144  * construct an isl_union_pw_multi_aff (A * C) -> (B, D).
3145  */
3146 __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_flat_range_product(
3147         __isl_take isl_union_pw_multi_aff *upma1,
3148         __isl_take isl_union_pw_multi_aff *upma2)
3149 {
3150         return bin_op(upma1, upma2, &flat_range_product_entry);
3151 }