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 MIT 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 /* Return a piecewise affine expression defined on the specified domain
  92  * that is equal to zero.
  93  */
  94 __isl_give isl_pw_aff *isl_pw_aff_zero_on_domain(__isl_take isl_local_space *ls)
  95 {
  96         return isl_pw_aff_from_aff(isl_aff_zero_on_domain(ls));
  97 }
  98
  99 /* Return an affine expression that is equal to the specified dimension
 100  * in "ls".
 101  */
 102 __isl_give isl_aff *isl_aff_var_on_domain(__isl_take isl_local_space *ls,
 103         enum isl_dim_type type, unsigned pos)
 104 {
 105         isl_space *space;
 106         isl_aff *aff;
 107
 108         if (!ls)
 109                 return NULL;
 110
 111         space = isl_local_space_get_space(ls);
 112         if (!space)
 113                 goto error;
 114         if (isl_space_is_map(space))
 115                 isl_die(isl_space_get_ctx(space), isl_error_invalid,
 116                         "expecting (parameter) set space", goto error);
 117         if (pos >= isl_local_space_dim(ls, type))
 118                 isl_die(isl_space_get_ctx(space), isl_error_invalid,
 119                         "position out of bounds", goto error);
 120
 121         isl_space_free(space);
 122         aff = isl_aff_alloc(ls);
 123         if (!aff)
 124                 return NULL;
 125
 126         pos += isl_local_space_offset(aff->ls, type);
 127
 128         isl_int_set_si(aff->v->el[0], 1);
 129         isl_seq_clr(aff->v->el + 1, aff->v->size - 1);
 130         isl_int_set_si(aff->v->el[1 + pos], 1);
 131
 132         return aff;
 133 error:
 134         isl_local_space_free(ls);
 135         isl_space_free(space);
 136         return NULL;
 137 }
 138
 139 /* Return a piecewise affine expression that is equal to
 140  * the specified dimension in "ls".
 141  */
 142 __isl_give isl_pw_aff *isl_pw_aff_var_on_domain(__isl_take isl_local_space *ls,
 143         enum isl_dim_type type, unsigned pos)
 144 {
 145         return isl_pw_aff_from_aff(isl_aff_var_on_domain(ls, type, pos));
 146 }
 147
 148 __isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff)
 149 {
 150         if (!aff)
 151                 return NULL;
 152
 153         aff->ref++;
 154         return aff;
 155 }
 156
 157 __isl_give isl_aff *isl_aff_dup(__isl_keep isl_aff *aff)
 158 {
 159         if (!aff)
 160                 return NULL;
 161
 162         return isl_aff_alloc_vec(isl_local_space_copy(aff->ls),
 163                                  isl_vec_copy(aff->v));
 164 }
 165
 166 __isl_give isl_aff *isl_aff_cow(__isl_take isl_aff *aff)
 167 {
 168         if (!aff)
 169                 return NULL;
 170
 171         if (aff->ref == 1)
 172                 return aff;
 173         aff->ref--;
 174         return isl_aff_dup(aff);
 175 }
 176
 177 void *isl_aff_free(__isl_take isl_aff *aff)
 178 {
 179         if (!aff)
 180                 return NULL;
 181
 182         if (--aff->ref > 0)
 183                 return NULL;
 184
 185         isl_local_space_free(aff->ls);
 186         isl_vec_free(aff->v);
 187
 188         free(aff);
 189
 190         return NULL;
 191 }
 192
 193 isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff)
 194 {
 195         return aff ? isl_local_space_get_ctx(aff->ls) : NULL;
 196 }
 197
 198 /* Externally, an isl_aff has a map space, but internally, the
 199  * ls field corresponds to the domain of that space.
 200  */
 201 int isl_aff_dim(__isl_keep isl_aff *aff, enum isl_dim_type type)
 202 {
 203         if (!aff)
 204                 return 0;
 205         if (type == isl_dim_out)
 206                 return 1;
 207         if (type == isl_dim_in)
 208                 type = isl_dim_set;
 209         return isl_local_space_dim(aff->ls, type);
 210 }
 211
 212 __isl_give isl_space *isl_aff_get_domain_space(__isl_keep isl_aff *aff)
 213 {
 214         return aff ? isl_local_space_get_space(aff->ls) : NULL;
 215 }
 216
 217 __isl_give isl_space *isl_aff_get_space(__isl_keep isl_aff *aff)
 218 {
 219         isl_space *space;
 220         if (!aff)
 221                 return NULL;
 222         space = isl_local_space_get_space(aff->ls);
 223         space = isl_space_from_domain(space);
 224         space = isl_space_add_dims(space, isl_dim_out, 1);
 225         return space;
 226 }
 227
 228 __isl_give isl_local_space *isl_aff_get_domain_local_space(
 229         __isl_keep isl_aff *aff)
 230 {
 231         return aff ? isl_local_space_copy(aff->ls) : NULL;
 232 }
 233
 234 __isl_give isl_local_space *isl_aff_get_local_space(__isl_keep isl_aff *aff)
 235 {
 236         isl_local_space *ls;
 237         if (!aff)
 238                 return NULL;
 239         ls = isl_local_space_copy(aff->ls);
 240         ls = isl_local_space_from_domain(ls);
 241         ls = isl_local_space_add_dims(ls, isl_dim_out, 1);
 242         return ls;
 243 }
 244
 245 /* Externally, an isl_aff has a map space, but internally, the
 246  * ls field corresponds to the domain of that space.
 247  */
 248 const char *isl_aff_get_dim_name(__isl_keep isl_aff *aff,
 249         enum isl_dim_type type, unsigned pos)
 250 {
 251         if (!aff)
 252                 return NULL;
 253         if (type == isl_dim_out)
 254                 return NULL;
 255         if (type == isl_dim_in)
 256                 type = isl_dim_set;
 257         return isl_local_space_get_dim_name(aff->ls, type, pos);
 258 }
 259
 260 __isl_give isl_aff *isl_aff_reset_domain_space(__isl_take isl_aff *aff,
 261         __isl_take isl_space *dim)
 262 {
 263         aff = isl_aff_cow(aff);
 264         if (!aff || !dim)
 265                 goto error;
 266
 267         aff->ls = isl_local_space_reset_space(aff->ls, dim);
 268         if (!aff->ls)
 269                 return isl_aff_free(aff);
 270
 271         return aff;
 272 error:
 273         isl_aff_free(aff);
 274         isl_space_free(dim);
 275         return NULL;
 276 }
 277
 278 /* Reset the space of "aff".  This function is called from isl_pw_templ.c
 279  * and doesn't know if the space of an element object is represented
 280  * directly or through its domain.  It therefore passes along both.
 281  */
 282 __isl_give isl_aff *isl_aff_reset_space_and_domain(__isl_take isl_aff *aff,
 283         __isl_take isl_space *space, __isl_take isl_space *domain)
 284 {
 285         isl_space_free(space);
 286         return isl_aff_reset_domain_space(aff, domain);
 287 }
 288
 289 /* Reorder the coefficients of the affine expression based
 290  * on the given reodering.
 291  * The reordering r is assumed to have been extended with the local
 292  * variables.
 293  */
 294 static __isl_give isl_vec *vec_reorder(__isl_take isl_vec *vec,
 295         __isl_take isl_reordering *r, int n_div)
 296 {
 297         isl_vec *res;
 298         int i;
 299
 300         if (!vec || !r)
 301                 goto error;
 302
 303         res = isl_vec_alloc(vec->ctx,
 304                             2 + isl_space_dim(r->dim, isl_dim_all) + n_div);
 305         isl_seq_cpy(res->el, vec->el, 2);
 306         isl_seq_clr(res->el + 2, res->size - 2);
 307         for (i = 0; i < r->len; ++i)
 308                 isl_int_set(res->el[2 + r->pos[i]], vec->el[2 + i]);
 309
 310         isl_reordering_free(r);
 311         isl_vec_free(vec);
 312         return res;
 313 error:
 314         isl_vec_free(vec);
 315         isl_reordering_free(r);
 316         return NULL;
 317 }
 318
 319 /* Reorder the dimensions of the domain of "aff" according
 320  * to the given reordering.
 321  */
 322 __isl_give isl_aff *isl_aff_realign_domain(__isl_take isl_aff *aff,
 323         __isl_take isl_reordering *r)
 324 {
 325         aff = isl_aff_cow(aff);
 326         if (!aff)
 327                 goto error;
 328
 329         r = isl_reordering_extend(r, aff->ls->div->n_row);
 330         aff->v = vec_reorder(aff->v, isl_reordering_copy(r),
 331                                 aff->ls->div->n_row);
 332         aff->ls = isl_local_space_realign(aff->ls, r);
 333
 334         if (!aff->v || !aff->ls)
 335                 return isl_aff_free(aff);
 336
 337         return aff;
 338 error:
 339         isl_aff_free(aff);
 340         isl_reordering_free(r);
 341         return NULL;
 342 }
 343
 344 __isl_give isl_aff *isl_aff_align_params(__isl_take isl_aff *aff,
 345         __isl_take isl_space *model)
 346 {
 347         if (!aff || !model)
 348                 goto error;
 349
 350         if (!isl_space_match(aff->ls->dim, isl_dim_param,
 351                              model, isl_dim_param)) {
 352                 isl_reordering *exp;
 353
 354                 model = isl_space_drop_dims(model, isl_dim_in,
 355                                         0, isl_space_dim(model, isl_dim_in));
 356                 model = isl_space_drop_dims(model, isl_dim_out,
 357                                         0, isl_space_dim(model, isl_dim_out));
 358                 exp = isl_parameter_alignment_reordering(aff->ls->dim, model);
 359                 exp = isl_reordering_extend_space(exp,
 360                                         isl_aff_get_domain_space(aff));
 361                 aff = isl_aff_realign_domain(aff, exp);
 362         }
 363
 364         isl_space_free(model);
 365         return aff;
 366 error:
 367         isl_space_free(model);
 368         isl_aff_free(aff);
 369         return NULL;
 370 }
 371
 372 int isl_aff_plain_is_zero(__isl_keep isl_aff *aff)
 373 {
 374         if (!aff)
 375                 return -1;
 376
 377         return isl_seq_first_non_zero(aff->v->el + 1, aff->v->size - 1) < 0;
 378 }
 379
 380 int isl_aff_plain_is_equal(__isl_keep isl_aff *aff1, __isl_keep isl_aff *aff2)
 381 {
 382         int equal;
 383
 384         if (!aff1 || !aff2)
 385                 return -1;
 386
 387         equal = isl_local_space_is_equal(aff1->ls, aff2->ls);
 388         if (equal < 0 || !equal)
 389                 return equal;
 390
 391         return isl_vec_is_equal(aff1->v, aff2->v);
 392 }
 393
 394 int isl_aff_get_denominator(__isl_keep isl_aff *aff, isl_int *v)
 395 {
 396         if (!aff)
 397                 return -1;
 398         isl_int_set(*v, aff->v->el[0]);
 399         return 0;
 400 }
 401
 402 int isl_aff_get_constant(__isl_keep isl_aff *aff, isl_int *v)
 403 {
 404         if (!aff)
 405                 return -1;
 406         isl_int_set(*v, aff->v->el[1]);
 407         return 0;
 408 }
 409
 410 int isl_aff_get_coefficient(__isl_keep isl_aff *aff,
 411         enum isl_dim_type type, int pos, isl_int *v)
 412 {
 413         if (!aff)
 414                 return -1;
 415
 416         if (type == isl_dim_out)
 417                 isl_die(aff->v->ctx, isl_error_invalid,
 418                         "output/set dimension does not have a coefficient",
 419                         return -1);
 420         if (type == isl_dim_in)
 421                 type = isl_dim_set;
 422
 423         if (pos >= isl_local_space_dim(aff->ls, type))
 424                 isl_die(aff->v->ctx, isl_error_invalid,
 425                         "position out of bounds", return -1);
 426
 427         pos += isl_local_space_offset(aff->ls, type);
 428         isl_int_set(*v, aff->v->el[1 + pos]);
 429
 430         return 0;
 431 }
 432
 433 __isl_give isl_aff *isl_aff_set_denominator(__isl_take isl_aff *aff, isl_int v)
 434 {
 435         aff = isl_aff_cow(aff);
 436         if (!aff)
 437                 return NULL;
 438
 439         aff->v = isl_vec_cow(aff->v);
 440         if (!aff->v)
 441                 return isl_aff_free(aff);
 442
 443         isl_int_set(aff->v->el[0], v);
 444
 445         return aff;
 446 }
 447
 448 __isl_give isl_aff *isl_aff_set_constant(__isl_take isl_aff *aff, isl_int v)
 449 {
 450         aff = isl_aff_cow(aff);
 451         if (!aff)
 452                 return NULL;
 453
 454         aff->v = isl_vec_cow(aff->v);
 455         if (!aff->v)
 456                 return isl_aff_free(aff);
 457
 458         isl_int_set(aff->v->el[1], v);
 459
 460         return aff;
 461 }
 462
 463 __isl_give isl_aff *isl_aff_add_constant(__isl_take isl_aff *aff, isl_int v)
 464 {
 465         if (isl_int_is_zero(v))
 466                 return 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         isl_int_addmul(aff->v->el[1], aff->v->el[0], v);
 477
 478         return aff;
 479 }
 480
 481 __isl_give isl_aff *isl_aff_add_constant_si(__isl_take isl_aff *aff, int v)
 482 {
 483         isl_int t;
 484
 485         isl_int_init(t);
 486         isl_int_set_si(t, v);
 487         aff = isl_aff_add_constant(aff, t);
 488         isl_int_clear(t);
 489
 490         return aff;
 491 }
 492
 493 /* Add "v" to the numerator of the constant term of "aff".
 494  */
 495 __isl_give isl_aff *isl_aff_add_constant_num(__isl_take isl_aff *aff, isl_int v)
 496 {
 497         if (isl_int_is_zero(v))
 498                 return aff;
 499
 500         aff = isl_aff_cow(aff);
 501         if (!aff)
 502                 return NULL;
 503
 504         aff->v = isl_vec_cow(aff->v);
 505         if (!aff->v)
 506                 return isl_aff_free(aff);
 507
 508         isl_int_add(aff->v->el[1], aff->v->el[1], v);
 509
 510         return aff;
 511 }
 512
 513 /* Add "v" to the numerator of the constant term of "aff".
 514  */
 515 __isl_give isl_aff *isl_aff_add_constant_num_si(__isl_take isl_aff *aff, int v)
 516 {
 517         isl_int t;
 518
 519         if (v == 0)
 520                 return aff;
 521
 522         isl_int_init(t);
 523         isl_int_set_si(t, v);
 524         aff = isl_aff_add_constant_num(aff, t);
 525         isl_int_clear(t);
 526
 527         return aff;
 528 }
 529
 530 __isl_give isl_aff *isl_aff_set_constant_si(__isl_take isl_aff *aff, int v)
 531 {
 532         aff = isl_aff_cow(aff);
 533         if (!aff)
 534                 return NULL;
 535
 536         aff->v = isl_vec_cow(aff->v);
 537         if (!aff->v)
 538                 return isl_aff_free(aff);
 539
 540         isl_int_set_si(aff->v->el[1], v);
 541
 542         return aff;
 543 }
 544
 545 __isl_give isl_aff *isl_aff_set_coefficient(__isl_take isl_aff *aff,
 546         enum isl_dim_type type, int pos, isl_int v)
 547 {
 548         if (!aff)
 549                 return NULL;
 550
 551         if (type == isl_dim_out)
 552                 isl_die(aff->v->ctx, isl_error_invalid,
 553                         "output/set dimension does not have a coefficient",
 554                         return isl_aff_free(aff));
 555         if (type == isl_dim_in)
 556                 type = isl_dim_set;
 557
 558         if (pos >= isl_local_space_dim(aff->ls, type))
 559                 isl_die(aff->v->ctx, isl_error_invalid,
 560                         "position out of bounds", return isl_aff_free(aff));
 561
 562         aff = isl_aff_cow(aff);
 563         if (!aff)
 564                 return NULL;
 565
 566         aff->v = isl_vec_cow(aff->v);
 567         if (!aff->v)
 568                 return isl_aff_free(aff);
 569
 570         pos += isl_local_space_offset(aff->ls, type);
 571         isl_int_set(aff->v->el[1 + pos], v);
 572
 573         return aff;
 574 }
 575
 576 __isl_give isl_aff *isl_aff_set_coefficient_si(__isl_take isl_aff *aff,
 577         enum isl_dim_type type, int pos, int v)
 578 {
 579         if (!aff)
 580                 return NULL;
 581
 582         if (type == isl_dim_out)
 583                 isl_die(aff->v->ctx, isl_error_invalid,
 584                         "output/set dimension does not have a coefficient",
 585                         return isl_aff_free(aff));
 586         if (type == isl_dim_in)
 587                 type = isl_dim_set;
 588
 589         if (pos >= isl_local_space_dim(aff->ls, type))
 590                 isl_die(aff->v->ctx, isl_error_invalid,
 591                         "position out of bounds", return isl_aff_free(aff));
 592
 593         aff = isl_aff_cow(aff);
 594         if (!aff)
 595                 return NULL;
 596
 597         aff->v = isl_vec_cow(aff->v);
 598         if (!aff->v)
 599                 return isl_aff_free(aff);
 600
 601         pos += isl_local_space_offset(aff->ls, type);
 602         isl_int_set_si(aff->v->el[1 + pos], v);
 603
 604         return aff;
 605 }
 606
 607 __isl_give isl_aff *isl_aff_add_coefficient(__isl_take isl_aff *aff,
 608         enum isl_dim_type type, int pos, isl_int v)
 609 {
 610         if (!aff)
 611                 return NULL;
 612
 613         if (type == isl_dim_out)
 614                 isl_die(aff->v->ctx, isl_error_invalid,
 615                         "output/set dimension does not have a coefficient",
 616                         return isl_aff_free(aff));
 617         if (type == isl_dim_in)
 618                 type = isl_dim_set;
 619
 620         if (pos >= isl_local_space_dim(aff->ls, type))
 621                 isl_die(aff->v->ctx, isl_error_invalid,
 622                         "position out of bounds", return isl_aff_free(aff));
 623
 624         aff = isl_aff_cow(aff);
 625         if (!aff)
 626                 return NULL;
 627
 628         aff->v = isl_vec_cow(aff->v);
 629         if (!aff->v)
 630                 return isl_aff_free(aff);
 631
 632         pos += isl_local_space_offset(aff->ls, type);
 633         isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v);
 634
 635         return aff;
 636 }
 637
 638 __isl_give isl_aff *isl_aff_add_coefficient_si(__isl_take isl_aff *aff,
 639         enum isl_dim_type type, int pos, int v)
 640 {
 641         isl_int t;
 642
 643         isl_int_init(t);
 644         isl_int_set_si(t, v);
 645         aff = isl_aff_add_coefficient(aff, type, pos, t);
 646         isl_int_clear(t);
 647
 648         return aff;
 649 }
 650
 651 __isl_give isl_aff *isl_aff_get_div(__isl_keep isl_aff *aff, int pos)
 652 {
 653         if (!aff)
 654                 return NULL;
 655
 656         return isl_local_space_get_div(aff->ls, pos);
 657 }
 658
 659 __isl_give isl_aff *isl_aff_neg(__isl_take isl_aff *aff)
 660 {
 661         aff = isl_aff_cow(aff);
 662         if (!aff)
 663                 return NULL;
 664         aff->v = isl_vec_cow(aff->v);
 665         if (!aff->v)
 666                 return isl_aff_free(aff);
 667
 668         isl_seq_neg(aff->v->el + 1, aff->v->el + 1, aff->v->size - 1);
 669
 670         return aff;
 671 }
 672
 673 /* Remove divs from the local space that do not appear in the affine
 674  * expression.
 675  * We currently only remove divs at the end.
 676  * Some intermediate divs may also not appear directly in the affine
 677  * expression, but we would also need to check that no other divs are
 678  * defined in terms of them.
 679  */
 680 __isl_give isl_aff *isl_aff_remove_unused_divs( __isl_take isl_aff *aff)
 681 {
 682         int pos;
 683         int off;
 684         int n;
 685
 686         if (!aff)
 687                 return NULL;
 688
 689         n = isl_local_space_dim(aff->ls, isl_dim_div);
 690         off = isl_local_space_offset(aff->ls, isl_dim_div);
 691
 692         pos = isl_seq_last_non_zero(aff->v->el + 1 + off, n) + 1;
 693         if (pos == n)
 694                 return aff;
 695
 696         aff = isl_aff_cow(aff);
 697         if (!aff)
 698                 return NULL;
 699
 700         aff->ls = isl_local_space_drop_dims(aff->ls, isl_dim_div, pos, n - pos);
 701         aff->v = isl_vec_drop_els(aff->v, 1 + off + pos, n - pos);
 702         if (!aff->ls || !aff->v)
 703                 return isl_aff_free(aff);
 704
 705         return aff;
 706 }
 707
 708 /* Given two affine expressions "p" of length p_len (including the
 709  * denominator and the constant term) and "subs" of length subs_len,
 710  * plug in "subs" for the variable at position "pos".
 711  * The variables of "subs" and "p" are assumed to match up to subs_len,
 712  * but "p" may have additional variables.
 713  * "v" is an initialized isl_int that can be used internally.
 714  *
 715  * In particular, if "p" represents the expression
 716  *
 717  *      (a i + g)/m
 718  *
 719  * with i the variable at position "pos" and "subs" represents the expression
 720  *
 721  *      f/d
 722  *
 723  * then the result represents the expression
 724  *
 725  *      (a f + d g)/(m d)
 726  *
 727  */
 728 void isl_seq_substitute(isl_int *p, int pos, isl_int *subs,
 729         int p_len, int subs_len, isl_int v)
 730 {
 731         isl_int_set(v, p[1 + pos]);
 732         isl_int_set_si(p[1 + pos], 0);
 733         isl_seq_combine(p + 1, subs[0], p + 1, v, subs + 1, subs_len - 1);
 734         isl_seq_scale(p + subs_len, p + subs_len, subs[0], p_len - subs_len);
 735         isl_int_mul(p[0], p[0], subs[0]);
 736 }
 737
 738 /* Look for any divs in the aff->ls with a denominator equal to one
 739  * and plug them into the affine expression and any subsequent divs
 740  * that may reference the div.
 741  */
 742 static __isl_give isl_aff *plug_in_integral_divs(__isl_take isl_aff *aff)
 743 {
 744         int i, n;
 745         int len;
 746         isl_int v;
 747         isl_vec *vec;
 748         isl_local_space *ls;
 749         unsigned pos;
 750
 751         if (!aff)
 752                 return NULL;
 753
 754         n = isl_local_space_dim(aff->ls, isl_dim_div);
 755         len = aff->v->size;
 756         for (i = 0; i < n; ++i) {
 757                 if (!isl_int_is_one(aff->ls->div->row[i][0]))
 758                         continue;
 759                 ls = isl_local_space_copy(aff->ls);
 760                 ls = isl_local_space_substitute_seq(ls, isl_dim_div, i,
 761                                 aff->ls->div->row[i], len, i + 1, n - (i + 1));
 762                 vec = isl_vec_copy(aff->v);
 763                 vec = isl_vec_cow(vec);
 764                 if (!ls || !vec)
 765                         goto error;
 766
 767                 isl_int_init(v);
 768
 769                 pos = isl_local_space_offset(aff->ls, isl_dim_div) + i;
 770                 isl_seq_substitute(vec->el, pos, aff->ls->div->row[i],
 771                                         len, len, v);
 772
 773                 isl_int_clear(v);
 774
 775                 isl_vec_free(aff->v);
 776                 aff->v = vec;
 777                 isl_local_space_free(aff->ls);
 778                 aff->ls = ls;
 779         }
 780
 781         return aff;
 782 error:
 783         isl_vec_free(vec);
 784         isl_local_space_free(ls);
 785         return isl_aff_free(aff);
 786 }
 787
 788 /* Look for any divs j that appear with a unit coefficient inside
 789  * the definitions of other divs i and plug them into the definitions
 790  * of the divs i.
 791  *
 792  * In particular, an expression of the form
 793  *
 794  *      floor((f(..) + floor(g(..)/n))/m)
 795  *
 796  * is simplified to
 797  *
 798  *      floor((n * f(..) + g(..))/(n * m))
 799  *
 800  * This simplification is correct because we can move the expression
 801  * f(..) into the inner floor in the original expression to obtain
 802  *
 803  *      floor(floor((n * f(..) + g(..))/n)/m)
 804  *
 805  * from which we can derive the simplified expression.
 806  */
 807 static __isl_give isl_aff *plug_in_unit_divs(__isl_take isl_aff *aff)
 808 {
 809         int i, j, n;
 810         int off;
 811
 812         if (!aff)
 813                 return NULL;
 814
 815         n = isl_local_space_dim(aff->ls, isl_dim_div);
 816         off = isl_local_space_offset(aff->ls, isl_dim_div);
 817         for (i = 1; i < n; ++i) {
 818                 for (j = 0; j < i; ++j) {
 819                         if (!isl_int_is_one(aff->ls->div->row[i][1 + off + j]))
 820                                 continue;
 821                         aff->ls = isl_local_space_substitute_seq(aff->ls,
 822                                 isl_dim_div, j, aff->ls->div->row[j],
 823                                 aff->v->size, i, 1);
 824                         if (!aff->ls)
 825                                 return isl_aff_free(aff);
 826                 }
 827         }
 828
 829         return aff;
 830 }
 831
 832 /* Swap divs "a" and "b" in "aff", which is assumed to be non-NULL.
 833  *
 834  * Even though this function is only called on isl_affs with a single
 835  * reference, we are careful to only change aff->v and aff->ls together.
 836  */
 837 static __isl_give isl_aff *swap_div(__isl_take isl_aff *aff, int a, int b)
 838 {
 839         unsigned off = isl_local_space_offset(aff->ls, isl_dim_div);
 840         isl_local_space *ls;
 841         isl_vec *v;
 842
 843         ls = isl_local_space_copy(aff->ls);
 844         ls = isl_local_space_swap_div(ls, a, b);
 845         v = isl_vec_copy(aff->v);
 846         v = isl_vec_cow(v);
 847         if (!ls || !v)
 848                 goto error;
 849
 850         isl_int_swap(v->el[1 + off + a], v->el[1 + off + b]);
 851         isl_vec_free(aff->v);
 852         aff->v = v;
 853         isl_local_space_free(aff->ls);
 854         aff->ls = ls;
 855
 856         return aff;
 857 error:
 858         isl_vec_free(v);
 859         isl_local_space_free(ls);
 860         return isl_aff_free(aff);
 861 }
 862
 863 /* Merge divs "a" and "b" in "aff", which is assumed to be non-NULL.
 864  *
 865  * We currently do not actually remove div "b", but simply add its
 866  * coefficient to that of "a" and then zero it out.
 867  */
 868 static __isl_give isl_aff *merge_divs(__isl_take isl_aff *aff, int a, int b)
 869 {
 870         unsigned off = isl_local_space_offset(aff->ls, isl_dim_div);
 871
 872         if (isl_int_is_zero(aff->v->el[1 + off + b]))
 873                 return aff;
 874
 875         aff->v = isl_vec_cow(aff->v);
 876         if (!aff->v)
 877                 return isl_aff_free(aff);
 878
 879         isl_int_add(aff->v->el[1 + off + a],
 880                     aff->v->el[1 + off + a], aff->v->el[1 + off + b]);
 881         isl_int_set_si(aff->v->el[1 + off + b], 0);
 882
 883         return aff;
 884 }
 885
 886 /* Sort the divs in the local space of "aff" according to
 887  * the comparison function "cmp_row" in isl_local_space.c,
 888  * combining the coefficients of identical divs.
 889  *
 890  * Reordering divs does not change the semantics of "aff",
 891  * so there is no need to call isl_aff_cow.
 892  * Moreover, this function is currently only called on isl_affs
 893  * with a single reference.
 894  */
 895 static __isl_give isl_aff *sort_divs(__isl_take isl_aff *aff)
 896 {
 897         int i, j, n;
 898         unsigned off;
 899
 900         if (!aff)
 901                 return NULL;
 902
 903         off = isl_local_space_offset(aff->ls, isl_dim_div);
 904         n = isl_aff_dim(aff, isl_dim_div);
 905         for (i = 1; i < n; ++i) {
 906                 for (j = i - 1; j >= 0; --j) {
 907                         int cmp = isl_mat_cmp_div(aff->ls->div, j, j + 1);
 908                         if (cmp < 0)
 909                                 break;
 910                         if (cmp == 0)
 911                                 aff = merge_divs(aff, j, j + 1);
 912                         else
 913                                 aff = swap_div(aff, j, j + 1);
 914                         if (!aff)
 915                                 return NULL;
 916                 }
 917         }
 918
 919         return aff;
 920 }
 921
 922 /* Normalize the representation of "aff".
 923  *
 924  * This function should only be called of "new" isl_affs, i.e.,
 925  * with only a single reference.  We therefore do not need to
 926  * worry about affecting other instances.
 927  */
 928 __isl_give isl_aff *isl_aff_normalize(__isl_take isl_aff *aff)
 929 {
 930         if (!aff)
 931                 return NULL;
 932         aff->v = isl_vec_normalize(aff->v);
 933         if (!aff->v)
 934                 return isl_aff_free(aff);
 935         aff = plug_in_integral_divs(aff);
 936         aff = plug_in_unit_divs(aff);
 937         aff = sort_divs(aff);
 938         aff = isl_aff_remove_unused_divs(aff);
 939         return aff;
 940 }
 941
 942 /* Given f, return floor(f).
 943  * If f is an integer expression, then just return f.
 944  * If f is a constant, then return the constant floor(f).
 945  * Otherwise, if f = g/m, write g = q m + r,
 946  * create a new div d = [r/m] and return the expression q + d.
 947  * The coefficients in r are taken to lie between -m/2 and m/2.
 948  */
 949 __isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff)
 950 {
 951         int i;
 952         int size;
 953         isl_ctx *ctx;
 954         isl_vec *div;
 955
 956         if (!aff)
 957                 return NULL;
 958
 959         if (isl_int_is_one(aff->v->el[0]))
 960                 return aff;
 961
 962         aff = isl_aff_cow(aff);
 963         if (!aff)
 964                 return NULL;
 965
 966         aff->v = isl_vec_cow(aff->v);
 967         if (!aff->v)
 968                 return isl_aff_free(aff);
 969
 970         if (isl_aff_is_cst(aff)) {
 971                 isl_int_fdiv_q(aff->v->el[1], aff->v->el[1], aff->v->el[0]);
 972                 isl_int_set_si(aff->v->el[0], 1);
 973                 return aff;
 974         }
 975
 976         div = isl_vec_copy(aff->v);
 977         div = isl_vec_cow(div);
 978         if (!div)
 979                 return isl_aff_free(aff);
 980
 981         ctx = isl_aff_get_ctx(aff);
 982         isl_int_fdiv_q(aff->v->el[0], aff->v->el[0], ctx->two);
 983         for (i = 1; i < aff->v->size; ++i) {
 984                 isl_int_fdiv_r(div->el[i], div->el[i], div->el[0]);
 985                 isl_int_fdiv_q(aff->v->el[i], aff->v->el[i], div->el[0]);
 986                 if (isl_int_gt(div->el[i], aff->v->el[0])) {
 987                         isl_int_sub(div->el[i], div->el[i], div->el[0]);
 988                         isl_int_add_ui(aff->v->el[i], aff->v->el[i], 1);
 989                 }
 990         }
 991
 992         aff->ls = isl_local_space_add_div(aff->ls, div);
 993         if (!aff->ls)
 994                 return isl_aff_free(aff);
 995
 996         size = aff->v->size;
 997         aff->v = isl_vec_extend(aff->v, size + 1);
 998         if (!aff->v)
 999                 return isl_aff_free(aff);
1000         isl_int_set_si(aff->v->el[0], 1);
1001         isl_int_set_si(aff->v->el[size], 1);
1002
1003         aff = isl_aff_normalize(aff);
1004
1005         return aff;
1006 }
1007
1008 /* Compute
1009  *
1010  *      aff mod m = aff - m * floor(aff/m)
1011  */
1012 __isl_give isl_aff *isl_aff_mod(__isl_take isl_aff *aff, isl_int m)
1013 {
1014         isl_aff *res;
1015
1016         res = isl_aff_copy(aff);
1017         aff = isl_aff_scale_down(aff, m);
1018         aff = isl_aff_floor(aff);
1019         aff = isl_aff_scale(aff, m);
1020         res = isl_aff_sub(res, aff);
1021
1022         return res;
1023 }
1024
1025 /* Compute
1026  *
1027  *      pwaff mod m = pwaff - m * floor(pwaff/m)
1028  */
1029 __isl_give isl_pw_aff *isl_pw_aff_mod(__isl_take isl_pw_aff *pwaff, isl_int m)
1030 {
1031         isl_pw_aff *res;
1032
1033         res = isl_pw_aff_copy(pwaff);
1034         pwaff = isl_pw_aff_scale_down(pwaff, m);
1035         pwaff = isl_pw_aff_floor(pwaff);
1036         pwaff = isl_pw_aff_scale(pwaff, m);
1037         res = isl_pw_aff_sub(res, pwaff);
1038
1039         return res;
1040 }
1041
1042 /* Given f, return ceil(f).
1043  * If f is an integer expression, then just return f.
1044  * Otherwise, let f be the expression
1045  *
1046  *      e/m
1047  *
1048  * then return
1049  *
1050  *      floor((e + m - 1)/m)
1051  */
1052 __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff)
1053 {
1054         if (!aff)
1055                 return NULL;
1056
1057         if (isl_int_is_one(aff->v->el[0]))
1058                 return aff;
1059
1060         aff = isl_aff_cow(aff);
1061         if (!aff)
1062                 return NULL;
1063         aff->v = isl_vec_cow(aff->v);
1064         if (!aff->v)
1065                 return isl_aff_free(aff);
1066
1067         isl_int_add(aff->v->el[1], aff->v->el[1], aff->v->el[0]);
1068         isl_int_sub_ui(aff->v->el[1], aff->v->el[1], 1);
1069         aff = isl_aff_floor(aff);
1070
1071         return aff;
1072 }
1073
1074 /* Apply the expansion computed by isl_merge_divs.
1075  * The expansion itself is given by "exp" while the resulting
1076  * list of divs is given by "div".
1077  */
1078 __isl_give isl_aff *isl_aff_expand_divs( __isl_take isl_aff *aff,
1079         __isl_take isl_mat *div, int *exp)
1080 {
1081         int i, j;
1082         int old_n_div;
1083         int new_n_div;
1084         int offset;
1085
1086         aff = isl_aff_cow(aff);
1087         if (!aff || !div)
1088                 goto error;
1089
1090         old_n_div = isl_local_space_dim(aff->ls, isl_dim_div);
1091         new_n_div = isl_mat_rows(div);
1092         if (new_n_div < old_n_div)
1093                 isl_die(isl_mat_get_ctx(div), isl_error_invalid,
1094                         "not an expansion", goto error);
1095
1096         aff->v = isl_vec_extend(aff->v, aff->v->size + new_n_div - old_n_div);
1097         if (!aff->v)
1098                 goto error;
1099
1100         offset = 1 + isl_local_space_offset(aff->ls, isl_dim_div);
1101         j = old_n_div - 1;
1102         for (i = new_n_div - 1; i >= 0; --i) {
1103                 if (j >= 0 && exp[j] == i) {
1104                         if (i != j)
1105                                 isl_int_swap(aff->v->el[offset + i],
1106                                              aff->v->el[offset + j]);
1107                         j--;
1108                 } else
1109                         isl_int_set_si(aff->v->el[offset + i], 0);
1110         }
1111
1112         aff->ls = isl_local_space_replace_divs(aff->ls, isl_mat_copy(div));
1113         if (!aff->ls)
1114                 goto error;
1115         isl_mat_free(div);
1116         return aff;
1117 error:
1118         isl_aff_free(aff);
1119         isl_mat_free(div);
1120         return NULL;
1121 }
1122
1123 /* Add two affine expressions that live in the same local space.
1124  */
1125 static __isl_give isl_aff *add_expanded(__isl_take isl_aff *aff1,
1126         __isl_take isl_aff *aff2)
1127 {
1128         isl_int gcd, f;
1129
1130         aff1 = isl_aff_cow(aff1);
1131         if (!aff1 || !aff2)
1132                 goto error;
1133
1134         aff1->v = isl_vec_cow(aff1->v);
1135         if (!aff1->v)
1136                 goto error;
1137
1138         isl_int_init(gcd);
1139         isl_int_init(f);
1140         isl_int_gcd(gcd, aff1->v->el[0], aff2->v->el[0]);
1141         isl_int_divexact(f, aff2->v->el[0], gcd);
1142         isl_seq_scale(aff1->v->el + 1, aff1->v->el + 1, f, aff1->v->size - 1);
1143         isl_int_divexact(f, aff1->v->el[0], gcd);
1144         isl_seq_addmul(aff1->v->el + 1, f, aff2->v->el + 1, aff1->v->size - 1);
1145         isl_int_divexact(f, aff2->v->el[0], gcd);
1146         isl_int_mul(aff1->v->el[0], aff1->v->el[0], f);
1147         isl_int_clear(f);
1148         isl_int_clear(gcd);
1149
1150         isl_aff_free(aff2);
1151         return aff1;
1152 error:
1153         isl_aff_free(aff1);
1154         isl_aff_free(aff2);
1155         return NULL;
1156 }
1157
1158 __isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
1159         __isl_take isl_aff *aff2)
1160 {
1161         isl_ctx *ctx;
1162         int *exp1 = NULL;
1163         int *exp2 = NULL;
1164         isl_mat *div;
1165
1166         if (!aff1 || !aff2)
1167                 goto error;
1168
1169         ctx = isl_aff_get_ctx(aff1);
1170         if (!isl_space_is_equal(aff1->ls->dim, aff2->ls->dim))
1171                 isl_die(ctx, isl_error_invalid,
1172                         "spaces don't match", goto error);
1173
1174         if (aff1->ls->div->n_row == 0 && aff2->ls->div->n_row == 0)
1175                 return add_expanded(aff1, aff2);
1176
1177         exp1 = isl_alloc_array(ctx, int, aff1->ls->div->n_row);
1178         exp2 = isl_alloc_array(ctx, int, aff2->ls->div->n_row);
1179         if (!exp1 || !exp2)
1180                 goto error;
1181
1182         div = isl_merge_divs(aff1->ls->div, aff2->ls->div, exp1, exp2);
1183         aff1 = isl_aff_expand_divs(aff1, isl_mat_copy(div), exp1);
1184         aff2 = isl_aff_expand_divs(aff2, div, exp2);
1185         free(exp1);
1186         free(exp2);
1187
1188         return add_expanded(aff1, aff2);
1189 error:
1190         free(exp1);
1191         free(exp2);
1192         isl_aff_free(aff1);
1193         isl_aff_free(aff2);
1194         return NULL;
1195 }
1196
1197 __isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
1198         __isl_take isl_aff *aff2)
1199 {
1200         return isl_aff_add(aff1, isl_aff_neg(aff2));
1201 }
1202
1203 __isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f)
1204 {
1205         isl_int gcd;
1206
1207         if (isl_int_is_one(f))
1208                 return aff;
1209
1210         aff = isl_aff_cow(aff);
1211         if (!aff)
1212                 return NULL;
1213         aff->v = isl_vec_cow(aff->v);
1214         if (!aff->v)
1215                 return isl_aff_free(aff);
1216
1217         isl_int_init(gcd);
1218         isl_int_gcd(gcd, aff->v->el[0], f);
1219         isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd);
1220         isl_int_divexact(gcd, f, gcd);
1221         isl_seq_scale(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
1222         isl_int_clear(gcd);
1223
1224         return aff;
1225 }
1226
1227 __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f)
1228 {
1229         isl_int gcd;
1230
1231         if (isl_int_is_one(f))
1232                 return aff;
1233
1234         aff = isl_aff_cow(aff);
1235         if (!aff)
1236                 return NULL;
1237
1238         if (isl_int_is_zero(f))
1239                 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
1240                         "cannot scale down by zero", return isl_aff_free(aff));
1241
1242         aff->v = isl_vec_cow(aff->v);
1243         if (!aff->v)
1244                 return isl_aff_free(aff);
1245
1246         isl_int_init(gcd);
1247         isl_seq_gcd(aff->v->el + 1, aff->v->size - 1, &gcd);
1248         isl_int_gcd(gcd, gcd, f);
1249         isl_seq_scale_down(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
1250         isl_int_divexact(gcd, f, gcd);
1251         isl_int_mul(aff->v->el[0], aff->v->el[0], gcd);
1252         isl_int_clear(gcd);
1253
1254         return aff;
1255 }
1256
1257 __isl_give isl_aff *isl_aff_scale_down_ui(__isl_take isl_aff *aff, unsigned f)
1258 {
1259         isl_int v;
1260
1261         if (f == 1)
1262                 return aff;
1263
1264         isl_int_init(v);
1265         isl_int_set_ui(v, f);
1266         aff = isl_aff_scale_down(aff, v);
1267         isl_int_clear(v);
1268
1269         return aff;
1270 }
1271
1272 __isl_give isl_aff *isl_aff_set_dim_name(__isl_take isl_aff *aff,
1273         enum isl_dim_type type, unsigned pos, const char *s)
1274 {
1275         aff = isl_aff_cow(aff);
1276         if (!aff)
1277                 return NULL;
1278         if (type == isl_dim_out)
1279                 isl_die(aff->v->ctx, isl_error_invalid,
1280                         "cannot set name of output/set dimension",
1281                         return isl_aff_free(aff));
1282         if (type == isl_dim_in)
1283                 type = isl_dim_set;
1284         aff->ls = isl_local_space_set_dim_name(aff->ls, type, pos, s);
1285         if (!aff->ls)
1286                 return isl_aff_free(aff);
1287
1288         return aff;
1289 }
1290
1291 __isl_give isl_aff *isl_aff_set_dim_id(__isl_take isl_aff *aff,
1292         enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
1293 {
1294         aff = isl_aff_cow(aff);
1295         if (!aff)
1296                 return isl_id_free(id);
1297         if (type == isl_dim_out)
1298                 isl_die(aff->v->ctx, isl_error_invalid,
1299                         "cannot set name of output/set dimension",
1300                         goto error);
1301         if (type == isl_dim_in)
1302                 type = isl_dim_set;
1303         aff->ls = isl_local_space_set_dim_id(aff->ls, type, pos, id);
1304         if (!aff->ls)
1305                 return isl_aff_free(aff);
1306
1307         return aff;
1308 error:
1309         isl_id_free(id);
1310         isl_aff_free(aff);
1311         return NULL;
1312 }
1313
1314 /* Exploit the equalities in "eq" to simplify the affine expression
1315  * and the expressions of the integer divisions in the local space.
1316  * The integer divisions in this local space are assumed to appear
1317  * as regular dimensions in "eq".
1318  */
1319 static __isl_give isl_aff *isl_aff_substitute_equalities_lifted(
1320         __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
1321 {
1322         int i, j;
1323         unsigned total;
1324         unsigned n_div;
1325
1326         if (!eq)
1327                 goto error;
1328         if (eq->n_eq == 0) {
1329                 isl_basic_set_free(eq);
1330                 return aff;
1331         }
1332
1333         aff = isl_aff_cow(aff);
1334         if (!aff)
1335                 goto error;
1336
1337         aff->ls = isl_local_space_substitute_equalities(aff->ls,
1338                                                         isl_basic_set_copy(eq));
1339         aff->v = isl_vec_cow(aff->v);
1340         if (!aff->ls || !aff->v)
1341                 goto error;
1342
1343         total = 1 + isl_space_dim(eq->dim, isl_dim_all);
1344         n_div = eq->n_div;
1345         for (i = 0; i < eq->n_eq; ++i) {
1346                 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
1347                 if (j < 0 || j == 0 || j >= total)
1348                         continue;
1349
1350                 isl_seq_elim(aff->v->el + 1, eq->eq[i], j, total,
1351                                 &aff->v->el[0]);
1352         }
1353
1354         isl_basic_set_free(eq);
1355         aff = isl_aff_normalize(aff);
1356         return aff;
1357 error:
1358         isl_basic_set_free(eq);
1359         isl_aff_free(aff);
1360         return NULL;
1361 }
1362
1363 /* Exploit the equalities in "eq" to simplify the affine expression
1364  * and the expressions of the integer divisions in the local space.
1365  */
1366 static __isl_give isl_aff *isl_aff_substitute_equalities(
1367         __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
1368 {
1369         int n_div;
1370
1371         if (!aff || !eq)
1372                 goto error;
1373         n_div = isl_local_space_dim(aff->ls, isl_dim_div);
1374         if (n_div > 0)
1375                 eq = isl_basic_set_add_dims(eq, isl_dim_set, n_div);
1376         return isl_aff_substitute_equalities_lifted(aff, eq);
1377 error:
1378         isl_basic_set_free(eq);
1379         isl_aff_free(aff);
1380         return NULL;
1381 }
1382
1383 /* Look for equalities among the variables shared by context and aff
1384  * and the integer divisions of aff, if any.
1385  * The equalities are then used to eliminate coefficients and/or integer
1386  * divisions from aff.
1387  */
1388 __isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff,
1389         __isl_take isl_set *context)
1390 {
1391         isl_basic_set *hull;
1392         int n_div;
1393
1394         if (!aff)
1395                 goto error;
1396         n_div = isl_local_space_dim(aff->ls, isl_dim_div);
1397         if (n_div > 0) {
1398                 isl_basic_set *bset;
1399                 isl_local_space *ls;
1400                 context = isl_set_add_dims(context, isl_dim_set, n_div);
1401                 ls = isl_aff_get_domain_local_space(aff);
1402                 bset = isl_basic_set_from_local_space(ls);
1403                 bset = isl_basic_set_lift(bset);
1404                 bset = isl_basic_set_flatten(bset);
1405                 context = isl_set_intersect(context,
1406                                             isl_set_from_basic_set(bset));
1407         }
1408
1409         hull = isl_set_affine_hull(context);
1410         return isl_aff_substitute_equalities_lifted(aff, hull);
1411 error:
1412         isl_aff_free(aff);
1413         isl_set_free(context);
1414         return NULL;
1415 }
1416
1417 __isl_give isl_aff *isl_aff_gist_params(__isl_take isl_aff *aff,
1418         __isl_take isl_set *context)
1419 {
1420         isl_set *dom_context = isl_set_universe(isl_aff_get_domain_space(aff));
1421         dom_context = isl_set_intersect_params(dom_context, context);
1422         return isl_aff_gist(aff, dom_context);
1423 }
1424
1425 /* Return a basic set containing those elements in the space
1426  * of aff where it is non-negative.
1427  * If "rational" is set, then return a rational basic set.
1428  */
1429 static __isl_give isl_basic_set *aff_nonneg_basic_set(
1430         __isl_take isl_aff *aff, int rational)
1431 {
1432         isl_constraint *ineq;
1433         isl_basic_set *bset;
1434
1435         ineq = isl_inequality_from_aff(aff);
1436
1437         bset = isl_basic_set_from_constraint(ineq);
1438         if (rational)
1439                 bset = isl_basic_set_set_rational(bset);
1440         bset = isl_basic_set_simplify(bset);
1441         return bset;
1442 }
1443
1444 /* Return a basic set containing those elements in the space
1445  * of aff where it is non-negative.
1446  */
1447 __isl_give isl_basic_set *isl_aff_nonneg_basic_set(__isl_take isl_aff *aff)
1448 {
1449         return aff_nonneg_basic_set(aff, 0);
1450 }
1451
1452 /* Return a basic set containing those elements in the domain space
1453  * of aff where it is negative.
1454  */
1455 __isl_give isl_basic_set *isl_aff_neg_basic_set(__isl_take isl_aff *aff)
1456 {
1457         aff = isl_aff_neg(aff);
1458         aff = isl_aff_add_constant_num_si(aff, -1);
1459         return isl_aff_nonneg_basic_set(aff);
1460 }
1461
1462 /* Return a basic set containing those elements in the space
1463  * of aff where it is zero.
1464  * If "rational" is set, then return a rational basic set.
1465  */
1466 static __isl_give isl_basic_set *aff_zero_basic_set(__isl_take isl_aff *aff,
1467         int rational)
1468 {
1469         isl_constraint *ineq;
1470         isl_basic_set *bset;
1471
1472         ineq = isl_equality_from_aff(aff);
1473
1474         bset = isl_basic_set_from_constraint(ineq);
1475         if (rational)
1476                 bset = isl_basic_set_set_rational(bset);
1477         bset = isl_basic_set_simplify(bset);
1478         return bset;
1479 }
1480
1481 /* Return a basic set containing those elements in the space
1482  * of aff where it is zero.
1483  */
1484 __isl_give isl_basic_set *isl_aff_zero_basic_set(__isl_take isl_aff *aff)
1485 {
1486         return aff_zero_basic_set(aff, 0);
1487 }
1488
1489 /* Return a basic set containing those elements in the shared space
1490  * of aff1 and aff2 where aff1 is greater than or equal to aff2.
1491  */
1492 __isl_give isl_basic_set *isl_aff_ge_basic_set(__isl_take isl_aff *aff1,
1493         __isl_take isl_aff *aff2)
1494 {
1495         aff1 = isl_aff_sub(aff1, aff2);
1496
1497         return isl_aff_nonneg_basic_set(aff1);
1498 }
1499
1500 /* Return a basic set containing those elements in the shared space
1501  * of aff1 and aff2 where aff1 is smaller than or equal to aff2.
1502  */
1503 __isl_give isl_basic_set *isl_aff_le_basic_set(__isl_take isl_aff *aff1,
1504         __isl_take isl_aff *aff2)
1505 {
1506         return isl_aff_ge_basic_set(aff2, aff1);
1507 }
1508
1509 __isl_give isl_aff *isl_aff_add_on_domain(__isl_keep isl_set *dom,
1510         __isl_take isl_aff *aff1, __isl_take isl_aff *aff2)
1511 {
1512         aff1 = isl_aff_add(aff1, aff2);
1513         aff1 = isl_aff_gist(aff1, isl_set_copy(dom));
1514         return aff1;
1515 }
1516
1517 int isl_aff_is_empty(__isl_keep isl_aff *aff)
1518 {
1519         if (!aff)
1520                 return -1;
1521
1522         return 0;
1523 }
1524
1525 /* Check whether the given affine expression has non-zero coefficient
1526  * for any dimension in the given range or if any of these dimensions
1527  * appear with non-zero coefficients in any of the integer divisions
1528  * involved in the affine expression.
1529  */
1530 int isl_aff_involves_dims(__isl_keep isl_aff *aff,
1531         enum isl_dim_type type, unsigned first, unsigned n)
1532 {
1533         int i;
1534         isl_ctx *ctx;
1535         int *active = NULL;
1536         int involves = 0;
1537
1538         if (!aff)
1539                 return -1;
1540         if (n == 0)
1541                 return 0;
1542
1543         ctx = isl_aff_get_ctx(aff);
1544         if (first + n > isl_aff_dim(aff, type))
1545                 isl_die(ctx, isl_error_invalid,
1546                         "range out of bounds", return -1);
1547
1548         active = isl_local_space_get_active(aff->ls, aff->v->el + 2);
1549         if (!active)
1550                 goto error;
1551
1552         first += isl_local_space_offset(aff->ls, type) - 1;
1553         for (i = 0; i < n; ++i)
1554                 if (active[first + i]) {
1555                         involves = 1;
1556                         break;
1557                 }
1558
1559         free(active);
1560
1561         return involves;
1562 error:
1563         free(active);
1564         return -1;
1565 }
1566
1567 __isl_give isl_aff *isl_aff_drop_dims(__isl_take isl_aff *aff,
1568         enum isl_dim_type type, unsigned first, unsigned n)
1569 {
1570         isl_ctx *ctx;
1571
1572         if (!aff)
1573                 return NULL;
1574         if (type == isl_dim_out)
1575                 isl_die(aff->v->ctx, isl_error_invalid,
1576                         "cannot drop output/set dimension",
1577                         return isl_aff_free(aff));
1578         if (type == isl_dim_in)
1579                 type = isl_dim_set;
1580         if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
1581                 return aff;
1582
1583         ctx = isl_aff_get_ctx(aff);
1584         if (first + n > isl_local_space_dim(aff->ls, type))
1585                 isl_die(ctx, isl_error_invalid, "range out of bounds",
1586                         return isl_aff_free(aff));
1587
1588         aff = isl_aff_cow(aff);
1589         if (!aff)
1590                 return NULL;
1591
1592         aff->ls = isl_local_space_drop_dims(aff->ls, type, first, n);
1593         if (!aff->ls)
1594                 return isl_aff_free(aff);
1595
1596         first += 1 + isl_local_space_offset(aff->ls, type);
1597         aff->v = isl_vec_drop_els(aff->v, first, n);
1598         if (!aff->v)
1599                 return isl_aff_free(aff);
1600
1601         return aff;
1602 }
1603
1604 /* Project the domain of the affine expression onto its parameter space.
1605  * The affine expression may not involve any of the domain dimensions.
1606  */
1607 __isl_give isl_aff *isl_aff_project_domain_on_params(__isl_take isl_aff *aff)
1608 {
1609         isl_space *space;
1610         unsigned n;
1611         int involves;
1612
1613         n = isl_aff_dim(aff, isl_dim_in);
1614         involves = isl_aff_involves_dims(aff, isl_dim_in, 0, n);
1615         if (involves < 0)
1616                 return isl_aff_free(aff);
1617         if (involves)
1618                 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
1619                     "affine expression involves some of the domain dimensions",
1620                     return isl_aff_free(aff));
1621         aff = isl_aff_drop_dims(aff, isl_dim_in, 0, n);
1622         space = isl_aff_get_domain_space(aff);
1623         space = isl_space_params(space);
1624         aff = isl_aff_reset_domain_space(aff, space);
1625         return aff;
1626 }
1627
1628 __isl_give isl_aff *isl_aff_insert_dims(__isl_take isl_aff *aff,
1629         enum isl_dim_type type, unsigned first, unsigned n)
1630 {
1631         isl_ctx *ctx;
1632
1633         if (!aff)
1634                 return NULL;
1635         if (type == isl_dim_out)
1636                 isl_die(aff->v->ctx, isl_error_invalid,
1637                         "cannot insert output/set dimensions",
1638                         return isl_aff_free(aff));
1639         if (type == isl_dim_in)
1640                 type = isl_dim_set;
1641         if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
1642                 return aff;
1643
1644         ctx = isl_aff_get_ctx(aff);
1645         if (first > isl_local_space_dim(aff->ls, type))
1646                 isl_die(ctx, isl_error_invalid, "position out of bounds",
1647                         return isl_aff_free(aff));
1648
1649         aff = isl_aff_cow(aff);
1650         if (!aff)
1651                 return NULL;
1652
1653         aff->ls = isl_local_space_insert_dims(aff->ls, type, first, n);
1654         if (!aff->ls)
1655                 return isl_aff_free(aff);
1656
1657         first += 1 + isl_local_space_offset(aff->ls, type);
1658         aff->v = isl_vec_insert_zero_els(aff->v, first, n);
1659         if (!aff->v)
1660                 return isl_aff_free(aff);
1661
1662         return aff;
1663 }
1664
1665 __isl_give isl_aff *isl_aff_add_dims(__isl_take isl_aff *aff,
1666         enum isl_dim_type type, unsigned n)
1667 {
1668         unsigned pos;
1669
1670         pos = isl_aff_dim(aff, type);
1671
1672         return isl_aff_insert_dims(aff, type, pos, n);
1673 }
1674
1675 __isl_give isl_pw_aff *isl_pw_aff_add_dims(__isl_take isl_pw_aff *pwaff,
1676         enum isl_dim_type type, unsigned n)
1677 {
1678         unsigned pos;
1679
1680         pos = isl_pw_aff_dim(pwaff, type);
1681
1682         return isl_pw_aff_insert_dims(pwaff, type, pos, n);
1683 }
1684
1685 __isl_give isl_pw_aff *isl_pw_aff_from_aff(__isl_take isl_aff *aff)
1686 {
1687         isl_set *dom = isl_set_universe(isl_aff_get_domain_space(aff));
1688         return isl_pw_aff_alloc(dom, aff);
1689 }
1690
1691 #undef PW
1692 #define PW isl_pw_aff
1693 #undef EL
1694 #define EL isl_aff
1695 #undef EL_IS_ZERO
1696 #define EL_IS_ZERO is_empty
1697 #undef ZERO
1698 #define ZERO empty
1699 #undef IS_ZERO
1700 #define IS_ZERO is_empty
1701 #undef FIELD
1702 #define FIELD aff
1703 #undef DEFAULT_IS_ZERO
1704 #define DEFAULT_IS_ZERO 0
1705
1706 #define NO_EVAL
1707 #define NO_OPT
1708 #define NO_MOVE_DIMS
1709 #define NO_LIFT
1710 #define NO_MORPH
1711
1712 #include <isl_pw_templ.c>
1713
1714 static __isl_give isl_set *align_params_pw_pw_set_and(
1715         __isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2,
1716         __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1717                                     __isl_take isl_pw_aff *pwaff2))
1718 {
1719         if (!pwaff1 || !pwaff2)
1720                 goto error;
1721         if (isl_space_match(pwaff1->dim, isl_dim_param,
1722                           pwaff2->dim, isl_dim_param))
1723                 return fn(pwaff1, pwaff2);
1724         if (!isl_space_has_named_params(pwaff1->dim) ||
1725             !isl_space_has_named_params(pwaff2->dim))
1726                 isl_die(isl_pw_aff_get_ctx(pwaff1), isl_error_invalid,
1727                         "unaligned unnamed parameters", goto error);
1728         pwaff1 = isl_pw_aff_align_params(pwaff1, isl_pw_aff_get_space(pwaff2));
1729         pwaff2 = isl_pw_aff_align_params(pwaff2, isl_pw_aff_get_space(pwaff1));
1730         return fn(pwaff1, pwaff2);
1731 error:
1732         isl_pw_aff_free(pwaff1);
1733         isl_pw_aff_free(pwaff2);
1734         return NULL;
1735 }
1736
1737 /* Compute a piecewise quasi-affine expression with a domain that
1738  * is the union of those of pwaff1 and pwaff2 and such that on each
1739  * cell, the quasi-affine expression is the better (according to cmp)
1740  * of those of pwaff1 and pwaff2.  If only one of pwaff1 or pwaff2
1741  * is defined on a given cell, then the associated expression
1742  * is the defined one.
1743  */
1744 static __isl_give isl_pw_aff *pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1745         __isl_take isl_pw_aff *pwaff2,
1746         __isl_give isl_basic_set *(*cmp)(__isl_take isl_aff *aff1,
1747                                         __isl_take isl_aff *aff2))
1748 {
1749         int i, j, n;
1750         isl_pw_aff *res;
1751         isl_ctx *ctx;
1752         isl_set *set;
1753
1754         if (!pwaff1 || !pwaff2)
1755                 goto error;
1756
1757         ctx = isl_space_get_ctx(pwaff1->dim);
1758         if (!isl_space_is_equal(pwaff1->dim, pwaff2->dim))
1759                 isl_die(ctx, isl_error_invalid,
1760                         "arguments should live in same space", goto error);
1761
1762         if (isl_pw_aff_is_empty(pwaff1)) {
1763                 isl_pw_aff_free(pwaff1);
1764                 return pwaff2;
1765         }
1766
1767         if (isl_pw_aff_is_empty(pwaff2)) {
1768                 isl_pw_aff_free(pwaff2);
1769                 return pwaff1;
1770         }
1771
1772         n = 2 * (pwaff1->n + 1) * (pwaff2->n + 1);
1773         res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n);
1774
1775         for (i = 0; i < pwaff1->n; ++i) {
1776                 set = isl_set_copy(pwaff1->p[i].set);
1777                 for (j = 0; j < pwaff2->n; ++j) {
1778                         struct isl_set *common;
1779                         isl_set *better;
1780
1781                         common = isl_set_intersect(
1782                                         isl_set_copy(pwaff1->p[i].set),
1783                                         isl_set_copy(pwaff2->p[j].set));
1784                         better = isl_set_from_basic_set(cmp(
1785                                         isl_aff_copy(pwaff2->p[j].aff),
1786                                         isl_aff_copy(pwaff1->p[i].aff)));
1787                         better = isl_set_intersect(common, better);
1788                         if (isl_set_plain_is_empty(better)) {
1789                                 isl_set_free(better);
1790                                 continue;
1791                         }
1792                         set = isl_set_subtract(set, isl_set_copy(better));
1793
1794                         res = isl_pw_aff_add_piece(res, better,
1795                                                 isl_aff_copy(pwaff2->p[j].aff));
1796                 }
1797                 res = isl_pw_aff_add_piece(res, set,
1798                                                 isl_aff_copy(pwaff1->p[i].aff));
1799         }
1800
1801         for (j = 0; j < pwaff2->n; ++j) {
1802                 set = isl_set_copy(pwaff2->p[j].set);
1803                 for (i = 0; i < pwaff1->n; ++i)
1804                         set = isl_set_subtract(set,
1805                                         isl_set_copy(pwaff1->p[i].set));
1806                 res = isl_pw_aff_add_piece(res, set,
1807                                                 isl_aff_copy(pwaff2->p[j].aff));
1808         }
1809
1810         isl_pw_aff_free(pwaff1);
1811         isl_pw_aff_free(pwaff2);
1812
1813         return res;
1814 error:
1815         isl_pw_aff_free(pwaff1);
1816         isl_pw_aff_free(pwaff2);
1817         return NULL;
1818 }
1819
1820 /* Compute a piecewise quasi-affine expression with a domain that
1821  * is the union of those of pwaff1 and pwaff2 and such that on each
1822  * cell, the quasi-affine expression is the maximum of those of pwaff1
1823  * and pwaff2.  If only one of pwaff1 or pwaff2 is defined on a given
1824  * cell, then the associated expression is the defined one.
1825  */
1826 static __isl_give isl_pw_aff *pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1827         __isl_take isl_pw_aff *pwaff2)
1828 {
1829         return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_ge_basic_set);
1830 }
1831
1832 __isl_give isl_pw_aff *isl_pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1833         __isl_take isl_pw_aff *pwaff2)
1834 {
1835         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2,
1836                                                         &pw_aff_union_max);
1837 }
1838
1839 /* Compute a piecewise quasi-affine expression with a domain that
1840  * is the union of those of pwaff1 and pwaff2 and such that on each
1841  * cell, the quasi-affine expression is the minimum of those of pwaff1
1842  * and pwaff2.  If only one of pwaff1 or pwaff2 is defined on a given
1843  * cell, then the associated expression is the defined one.
1844  */
1845 static __isl_give isl_pw_aff *pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1846         __isl_take isl_pw_aff *pwaff2)
1847 {
1848         return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_le_basic_set);
1849 }
1850
1851 __isl_give isl_pw_aff *isl_pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1852         __isl_take isl_pw_aff *pwaff2)
1853 {
1854         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2,
1855                                                         &pw_aff_union_min);
1856 }
1857
1858 __isl_give isl_pw_aff *isl_pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1859         __isl_take isl_pw_aff *pwaff2, int max)
1860 {
1861         if (max)
1862                 return isl_pw_aff_union_max(pwaff1, pwaff2);
1863         else
1864                 return isl_pw_aff_union_min(pwaff1, pwaff2);
1865 }
1866
1867 /* Construct a map with as domain the domain of pwaff and
1868  * one-dimensional range corresponding to the affine expressions.
1869  */
1870 static __isl_give isl_map *map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1871 {
1872         int i;
1873         isl_space *dim;
1874         isl_map *map;
1875
1876         if (!pwaff)
1877                 return NULL;
1878
1879         dim = isl_pw_aff_get_space(pwaff);
1880         map = isl_map_empty(dim);
1881
1882         for (i = 0; i < pwaff->n; ++i) {
1883                 isl_basic_map *bmap;
1884                 isl_map *map_i;
1885
1886                 bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
1887                 map_i = isl_map_from_basic_map(bmap);
1888                 map_i = isl_map_intersect_domain(map_i,
1889                                                 isl_set_copy(pwaff->p[i].set));
1890                 map = isl_map_union_disjoint(map, map_i);
1891         }
1892
1893         isl_pw_aff_free(pwaff);
1894
1895         return map;
1896 }
1897
1898 /* Construct a map with as domain the domain of pwaff and
1899  * one-dimensional range corresponding to the affine expressions.
1900  */
1901 __isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1902 {
1903         if (!pwaff)
1904                 return NULL;
1905         if (isl_space_is_set(pwaff->dim))
1906                 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1907                         "space of input is not a map",
1908                         return isl_pw_aff_free(pwaff));
1909         return map_from_pw_aff(pwaff);
1910 }
1911
1912 /* Construct a one-dimensional set with as parameter domain
1913  * the domain of pwaff and the single set dimension
1914  * corresponding to the affine expressions.
1915  */
1916 __isl_give isl_set *isl_set_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1917 {
1918         if (!pwaff)
1919                 return NULL;
1920         if (!isl_space_is_set(pwaff->dim))
1921                 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1922                         "space of input is not a set",
1923                         return isl_pw_aff_free(pwaff));
1924         return map_from_pw_aff(pwaff);
1925 }
1926
1927 /* Return a set containing those elements in the domain
1928  * of pwaff where it is non-negative.
1929  */
1930 __isl_give isl_set *isl_pw_aff_nonneg_set(__isl_take isl_pw_aff *pwaff)
1931 {
1932         int i;
1933         isl_set *set;
1934
1935         if (!pwaff)
1936                 return NULL;
1937
1938         set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1939
1940         for (i = 0; i < pwaff->n; ++i) {
1941                 isl_basic_set *bset;
1942                 isl_set *set_i;
1943                 int rational;
1944
1945                 rational = isl_set_has_rational(pwaff->p[i].set);
1946                 bset = aff_nonneg_basic_set(isl_aff_copy(pwaff->p[i].aff),
1947                                                 rational);
1948                 set_i = isl_set_from_basic_set(bset);
1949                 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1950                 set = isl_set_union_disjoint(set, set_i);
1951         }
1952
1953         isl_pw_aff_free(pwaff);
1954
1955         return set;
1956 }
1957
1958 /* Return a set containing those elements in the domain
1959  * of pwaff where it is zero (if complement is 0) or not zero
1960  * (if complement is 1).
1961  */
1962 static __isl_give isl_set *pw_aff_zero_set(__isl_take isl_pw_aff *pwaff,
1963         int complement)
1964 {
1965         int i;
1966         isl_set *set;
1967
1968         if (!pwaff)
1969                 return NULL;
1970
1971         set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1972
1973         for (i = 0; i < pwaff->n; ++i) {
1974                 isl_basic_set *bset;
1975                 isl_set *set_i, *zero;
1976                 int rational;
1977
1978                 rational = isl_set_has_rational(pwaff->p[i].set);
1979                 bset = aff_zero_basic_set(isl_aff_copy(pwaff->p[i].aff),
1980                                                 rational);
1981                 zero = isl_set_from_basic_set(bset);
1982                 set_i = isl_set_copy(pwaff->p[i].set);
1983                 if (complement)
1984                         set_i = isl_set_subtract(set_i, zero);
1985                 else
1986                         set_i = isl_set_intersect(set_i, zero);
1987                 set = isl_set_union_disjoint(set, set_i);
1988         }
1989
1990         isl_pw_aff_free(pwaff);
1991
1992         return set;
1993 }
1994
1995 /* Return a set containing those elements in the domain
1996  * of pwaff where it is zero.
1997  */
1998 __isl_give isl_set *isl_pw_aff_zero_set(__isl_take isl_pw_aff *pwaff)
1999 {
2000         return pw_aff_zero_set(pwaff, 0);
2001 }
2002
2003 /* Return a set containing those elements in the domain
2004  * of pwaff where it is not zero.
2005  */
2006 __isl_give isl_set *isl_pw_aff_non_zero_set(__isl_take isl_pw_aff *pwaff)
2007 {
2008         return pw_aff_zero_set(pwaff, 1);
2009 }
2010
2011 /* Return a set containing those elements in the shared domain
2012  * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
2013  *
2014  * We compute the difference on the shared domain and then construct
2015  * the set of values where this difference is non-negative.
2016  * If strict is set, we first subtract 1 from the difference.
2017  * If equal is set, we only return the elements where pwaff1 and pwaff2
2018  * are equal.
2019  */
2020 static __isl_give isl_set *pw_aff_gte_set(__isl_take isl_pw_aff *pwaff1,
2021         __isl_take isl_pw_aff *pwaff2, int strict, int equal)
2022 {
2023         isl_set *set1, *set2;
2024
2025         set1 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff1));
2026         set2 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff2));
2027         set1 = isl_set_intersect(set1, set2);
2028         pwaff1 = isl_pw_aff_intersect_domain(pwaff1, isl_set_copy(set1));
2029         pwaff2 = isl_pw_aff_intersect_domain(pwaff2, isl_set_copy(set1));
2030         pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_neg(pwaff2));
2031
2032         if (strict) {
2033                 isl_space *dim = isl_set_get_space(set1);
2034                 isl_aff *aff;
2035                 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
2036                 aff = isl_aff_add_constant_si(aff, -1);
2037                 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_alloc(set1, aff));
2038         } else
2039                 isl_set_free(set1);
2040
2041         if (equal)
2042                 return isl_pw_aff_zero_set(pwaff1);
2043         return isl_pw_aff_nonneg_set(pwaff1);
2044 }
2045
2046 /* Return a set containing those elements in the shared domain
2047  * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
2048  */
2049 static __isl_give isl_set *pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
2050         __isl_take isl_pw_aff *pwaff2)
2051 {
2052         return pw_aff_gte_set(pwaff1, pwaff2, 0, 1);
2053 }
2054
2055 __isl_give isl_set *isl_pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
2056         __isl_take isl_pw_aff *pwaff2)
2057 {
2058         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_eq_set);
2059 }
2060
2061 /* Return a set containing those elements in the shared domain
2062  * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
2063  */
2064 static __isl_give isl_set *pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
2065         __isl_take isl_pw_aff *pwaff2)
2066 {
2067         return pw_aff_gte_set(pwaff1, pwaff2, 0, 0);
2068 }
2069
2070 __isl_give isl_set *isl_pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
2071         __isl_take isl_pw_aff *pwaff2)
2072 {
2073         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ge_set);
2074 }
2075
2076 /* Return a set containing those elements in the shared domain
2077  * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
2078  */
2079 static __isl_give isl_set *pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
2080         __isl_take isl_pw_aff *pwaff2)
2081 {
2082         return pw_aff_gte_set(pwaff1, pwaff2, 1, 0);
2083 }
2084
2085 __isl_give isl_set *isl_pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
2086         __isl_take isl_pw_aff *pwaff2)
2087 {
2088         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_gt_set);
2089 }
2090
2091 __isl_give isl_set *isl_pw_aff_le_set(__isl_take isl_pw_aff *pwaff1,
2092         __isl_take isl_pw_aff *pwaff2)
2093 {
2094         return isl_pw_aff_ge_set(pwaff2, pwaff1);
2095 }
2096
2097 __isl_give isl_set *isl_pw_aff_lt_set(__isl_take isl_pw_aff *pwaff1,
2098         __isl_take isl_pw_aff *pwaff2)
2099 {
2100         return isl_pw_aff_gt_set(pwaff2, pwaff1);
2101 }
2102
2103 /* Return a set containing those elements in the shared domain
2104  * of the elements of list1 and list2 where each element in list1
2105  * has the relation specified by "fn" with each element in list2.
2106  */
2107 static __isl_give isl_set *pw_aff_list_set(__isl_take isl_pw_aff_list *list1,
2108         __isl_take isl_pw_aff_list *list2,
2109         __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
2110                                     __isl_take isl_pw_aff *pwaff2))
2111 {
2112         int i, j;
2113         isl_ctx *ctx;
2114         isl_set *set;
2115
2116         if (!list1 || !list2)
2117                 goto error;
2118
2119         ctx = isl_pw_aff_list_get_ctx(list1);
2120         if (list1->n < 1 || list2->n < 1)
2121                 isl_die(ctx, isl_error_invalid,
2122                         "list should contain at least one element", goto error);
2123
2124         set = isl_set_universe(isl_pw_aff_get_domain_space(list1->p[0]));
2125         for (i = 0; i < list1->n; ++i)
2126                 for (j = 0; j < list2->n; ++j) {
2127                         isl_set *set_ij;
2128
2129                         set_ij = fn(isl_pw_aff_copy(list1->p[i]),
2130                                     isl_pw_aff_copy(list2->p[j]));
2131                         set = isl_set_intersect(set, set_ij);
2132                 }
2133
2134         isl_pw_aff_list_free(list1);
2135         isl_pw_aff_list_free(list2);
2136         return set;
2137 error:
2138         isl_pw_aff_list_free(list1);
2139         isl_pw_aff_list_free(list2);
2140         return NULL;
2141 }
2142
2143 /* Return a set containing those elements in the shared domain
2144  * of the elements of list1 and list2 where each element in list1
2145  * is equal to each element in list2.
2146  */
2147 __isl_give isl_set *isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list *list1,
2148         __isl_take isl_pw_aff_list *list2)
2149 {
2150         return pw_aff_list_set(list1, list2, &isl_pw_aff_eq_set);
2151 }
2152
2153 __isl_give isl_set *isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list *list1,
2154         __isl_take isl_pw_aff_list *list2)
2155 {
2156         return pw_aff_list_set(list1, list2, &isl_pw_aff_ne_set);
2157 }
2158
2159 /* Return a set containing those elements in the shared domain
2160  * of the elements of list1 and list2 where each element in list1
2161  * is less than or equal to each element in list2.
2162  */
2163 __isl_give isl_set *isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list *list1,
2164         __isl_take isl_pw_aff_list *list2)
2165 {
2166         return pw_aff_list_set(list1, list2, &isl_pw_aff_le_set);
2167 }
2168
2169 __isl_give isl_set *isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list *list1,
2170         __isl_take isl_pw_aff_list *list2)
2171 {
2172         return pw_aff_list_set(list1, list2, &isl_pw_aff_lt_set);
2173 }
2174
2175 __isl_give isl_set *isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list *list1,
2176         __isl_take isl_pw_aff_list *list2)
2177 {
2178         return pw_aff_list_set(list1, list2, &isl_pw_aff_ge_set);
2179 }
2180
2181 __isl_give isl_set *isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list *list1,
2182         __isl_take isl_pw_aff_list *list2)
2183 {
2184         return pw_aff_list_set(list1, list2, &isl_pw_aff_gt_set);
2185 }
2186
2187
2188 /* Return a set containing those elements in the shared domain
2189  * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
2190  */
2191 static __isl_give isl_set *pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
2192         __isl_take isl_pw_aff *pwaff2)
2193 {
2194         isl_set *set_lt, *set_gt;
2195
2196         set_lt = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1),
2197                                    isl_pw_aff_copy(pwaff2));
2198         set_gt = isl_pw_aff_gt_set(pwaff1, pwaff2);
2199         return isl_set_union_disjoint(set_lt, set_gt);
2200 }
2201
2202 __isl_give isl_set *isl_pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
2203         __isl_take isl_pw_aff *pwaff2)
2204 {
2205         return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ne_set);
2206 }
2207
2208 __isl_give isl_pw_aff *isl_pw_aff_scale_down(__isl_take isl_pw_aff *pwaff,
2209         isl_int v)
2210 {
2211         int i;
2212
2213         if (isl_int_is_one(v))
2214                 return pwaff;
2215         if (!isl_int_is_pos(v))
2216                 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
2217                         "factor needs to be positive",
2218                         return isl_pw_aff_free(pwaff));
2219         pwaff = isl_pw_aff_cow(pwaff);
2220         if (!pwaff)
2221                 return NULL;
2222         if (pwaff->n == 0)
2223                 return pwaff;
2224
2225         for (i = 0; i < pwaff->n; ++i) {
2226                 pwaff->p[i].aff = isl_aff_scale_down(pwaff->p[i].aff, v);
2227                 if (!pwaff->p[i].aff)
2228                         return isl_pw_aff_free(pwaff);
2229         }
2230
2231         return pwaff;
2232 }
2233
2234 __isl_give isl_pw_aff *isl_pw_aff_floor(__isl_take isl_pw_aff *pwaff)
2235 {
2236         int i;
2237
2238         pwaff = isl_pw_aff_cow(pwaff);
2239         if (!pwaff)
2240                 return NULL;
2241         if (pwaff->n == 0)
2242                 return pwaff;
2243
2244         for (i = 0; i < pwaff->n; ++i) {
2245                 pwaff->p[i].aff = isl_aff_floor(pwaff->p[i].aff);
2246                 if (!pwaff->p[i].aff)
2247                         return isl_pw_aff_free(pwaff);
2248         }
2249
2250         return pwaff;
2251 }
2252
2253 __isl_give isl_pw_aff *isl_pw_aff_ceil(__isl_take isl_pw_aff *pwaff)
2254 {
2255         int i;
2256
2257         pwaff = isl_pw_aff_cow(pwaff);
2258         if (!pwaff)
2259                 return NULL;
2260         if (pwaff->n == 0)
2261                 return pwaff;
2262
2263         for (i = 0; i < pwaff->n; ++i) {
2264                 pwaff->p[i].aff = isl_aff_ceil(pwaff->p[i].aff);
2265                 if (!pwaff->p[i].aff)
2266                         return isl_pw_aff_free(pwaff);
2267         }
2268
2269         return pwaff;
2270 }
2271
2272 /* Assuming that "cond1" and "cond2" are disjoint,
2273  * return an affine expression that is equal to pwaff1 on cond1
2274  * and to pwaff2 on cond2.
2275  */
2276 static __isl_give isl_pw_aff *isl_pw_aff_select(
2277         __isl_take isl_set *cond1, __isl_take isl_pw_aff *pwaff1,
2278         __isl_take isl_set *cond2, __isl_take isl_pw_aff *pwaff2)
2279 {
2280         pwaff1 = isl_pw_aff_intersect_domain(pwaff1, cond1);
2281         pwaff2 = isl_pw_aff_intersect_domain(pwaff2, cond2);
2282
2283         return isl_pw_aff_add_disjoint(pwaff1, pwaff2);
2284 }
2285
2286 /* Return an affine expression that is equal to pwaff_true for elements
2287  * where "cond" is non-zero and to pwaff_false for elements where "cond"
2288  * is zero.
2289  * That is, return cond ? pwaff_true : pwaff_false;
2290  */
2291 __isl_give isl_pw_aff *isl_pw_aff_cond(__isl_take isl_pw_aff *cond,
2292         __isl_take isl_pw_aff *pwaff_true, __isl_take isl_pw_aff *pwaff_false)
2293 {
2294         isl_set *cond_true, *cond_false;
2295
2296         cond_true = isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond));
2297         cond_false = isl_pw_aff_zero_set(cond);
2298         return isl_pw_aff_select(cond_true, pwaff_true,
2299                                  cond_false, pwaff_false);
2300 }
2301
2302 int isl_aff_is_cst(__isl_keep isl_aff *aff)
2303 {
2304         if (!aff)
2305                 return -1;
2306
2307         return isl_seq_first_non_zero(aff->v->el + 2, aff->v->size - 2) == -1;
2308 }
2309
2310 /* Check whether pwaff is a piecewise constant.
2311  */
2312 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff)
2313 {
2314         int i;
2315
2316         if (!pwaff)
2317                 return -1;
2318
2319         for (i = 0; i < pwaff->n; ++i) {
2320                 int is_cst = isl_aff_is_cst(pwaff->p[i].aff);
2321                 if (is_cst < 0 || !is_cst)
2322                         return is_cst;
2323         }
2324
2325         return 1;
2326 }
2327
2328 __isl_give isl_aff *isl_aff_mul(__isl_take isl_aff *aff1,
2329         __isl_take isl_aff *aff2)
2330 {
2331         if (!isl_aff_is_cst(aff2) && isl_aff_is_cst(aff1))
2332                 return isl_aff_mul(aff2, aff1);
2333
2334         if (!isl_aff_is_cst(aff2))
2335                 isl_die(isl_aff_get_ctx(aff1), isl_error_invalid,
2336                         "at least one affine expression should be constant",
2337                         goto error);
2338
2339         aff1 = isl_aff_cow(aff1);
2340         if (!aff1 || !aff2)
2341                 goto error;
2342
2343         aff1 = isl_aff_scale(aff1, aff2->v->el[1]);
2344         aff1 = isl_aff_scale_down(aff1, aff2->v->el[0]);
2345
2346         isl_aff_free(aff2);
2347         return aff1;
2348 error:
2349         isl_aff_free(aff1);
2350         isl_aff_free(aff2);
2351         return NULL;
2352 }
2353
2354 /* Divide "aff1" by "aff2", assuming "aff2" is a piecewise constant.
2355  */
2356 __isl_give isl_aff *isl_aff_div(__isl_take isl_aff *aff1,
2357         __isl_take isl_aff *aff2)
2358 {
2359         int is_cst;
2360         int neg;
2361
2362         is_cst = isl_aff_is_cst(aff2);
2363         if (is_cst < 0)
2364                 goto error;
2365         if (!is_cst)
2366                 isl_die(isl_aff_get_ctx(aff2), isl_error_invalid,
2367                         "second argument should be a constant", goto error);
2368
2369         if (!aff2)
2370                 goto error;
2371
2372         neg = isl_int_is_neg(aff2->v->el[1]);
2373         if (neg) {
2374                 isl_int_neg(aff2->v->el[0], aff2->v->el[0]);
2375                 isl_int_neg(aff2->v->el[1], aff2->v->el[1]);
2376         }
2377
2378         aff1 = isl_aff_scale(aff1, aff2->v->el[0]);
2379         aff1 = isl_aff_scale_down(aff1, aff2->v->el[1]);
2380
2381         if (neg) {
2382                 isl_int_neg(aff2->v->el[0], aff2->v->el[0]);
2383                 isl_int_neg(aff2->v->el[1], aff2->v->el[1]);
2384         }
2385
2386         isl_aff_free(aff2);
2387         return aff1;
2388 error:
2389         isl_aff_free(aff1);
2390         isl_aff_free(aff2);
2391         return NULL;
2392 }
2393
2394 static __isl_give isl_pw_aff *pw_aff_add(__isl_take isl_pw_aff *pwaff1,
2395         __isl_take isl_pw_aff *pwaff2)
2396 {
2397         return isl_pw_aff_on_shared_domain(pwaff1, pwaff2, &isl_aff_add);
2398 }
2399
2400 __isl_give isl_pw_aff *isl_pw_aff_add(__isl_take isl_pw_aff *pwaff1,
2401         __isl_take isl_pw_aff *pwaff2)
2402 {
2403         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_add);
2404 }
2405
2406 __isl_give isl_pw_aff *isl_pw_aff_union_add(__isl_take isl_pw_aff *pwaff1,
2407         __isl_take isl_pw_aff *pwaff2)
2408 {
2409         return isl_pw_aff_union_add_(pwaff1, pwaff2);
2410 }
2411
2412 static __isl_give isl_pw_aff *pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
2413         __isl_take isl_pw_aff *pwaff2)
2414 {
2415         return isl_pw_aff_on_shared_domain(pwaff1, pwaff2, &isl_aff_mul);
2416 }
2417
2418 __isl_give isl_pw_aff *isl_pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
2419         __isl_take isl_pw_aff *pwaff2)
2420 {
2421         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_mul);
2422 }
2423
2424 static __isl_give isl_pw_aff *pw_aff_div(__isl_take isl_pw_aff *pa1,
2425         __isl_take isl_pw_aff *pa2)
2426 {
2427         return isl_pw_aff_on_shared_domain(pa1, pa2, &isl_aff_div);
2428 }
2429
2430 /* Divide "pa1" by "pa2", assuming "pa2" is a piecewise constant.
2431  */
2432 __isl_give isl_pw_aff *isl_pw_aff_div(__isl_take isl_pw_aff *pa1,
2433         __isl_take isl_pw_aff *pa2)
2434 {
2435         int is_cst;
2436
2437         is_cst = isl_pw_aff_is_cst(pa2);
2438         if (is_cst < 0)
2439                 goto error;
2440         if (!is_cst)
2441                 isl_die(isl_pw_aff_get_ctx(pa2), isl_error_invalid,
2442                         "second argument should be a piecewise constant",
2443                         goto error);
2444         return isl_pw_aff_align_params_pw_pw_and(pa1, pa2, &pw_aff_div);
2445 error:
2446         isl_pw_aff_free(pa1);
2447         isl_pw_aff_free(pa2);
2448         return NULL;
2449 }
2450
2451 /* Compute the quotient of the integer division of "pa1" by "pa2"
2452  * with rounding towards zero.
2453  * "pa2" is assumed to be a piecewise constant.
2454  *
2455  * In particular, return
2456  *
2457  *      pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2)
2458  *
2459  */
2460 __isl_give isl_pw_aff *isl_pw_aff_tdiv_q(__isl_take isl_pw_aff *pa1,
2461         __isl_take isl_pw_aff *pa2)
2462 {
2463         int is_cst;
2464         isl_set *cond;
2465         isl_pw_aff *f, *c;
2466
2467         is_cst = isl_pw_aff_is_cst(pa2);
2468         if (is_cst < 0)
2469                 goto error;
2470         if (!is_cst)
2471                 isl_die(isl_pw_aff_get_ctx(pa2), isl_error_invalid,
2472                         "second argument should be a piecewise constant",
2473                         goto error);
2474
2475         pa1 = isl_pw_aff_div(pa1, pa2);
2476
2477         cond = isl_pw_aff_nonneg_set(isl_pw_aff_copy(pa1));
2478         f = isl_pw_aff_floor(isl_pw_aff_copy(pa1));
2479         c = isl_pw_aff_ceil(pa1);
2480         return isl_pw_aff_cond(isl_set_indicator_function(cond), f, c);
2481 error:
2482         isl_pw_aff_free(pa1);
2483         isl_pw_aff_free(pa2);
2484         return NULL;
2485 }
2486
2487 /* Compute the remainder of the integer division of "pa1" by "pa2"
2488  * with rounding towards zero.
2489  * "pa2" is assumed to be a piecewise constant.
2490  *
2491  * In particular, return
2492  *
2493  *      pa1 - pa2 * (pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2))
2494  *
2495  */
2496 __isl_give isl_pw_aff *isl_pw_aff_tdiv_r(__isl_take isl_pw_aff *pa1,
2497         __isl_take isl_pw_aff *pa2)
2498 {
2499         int is_cst;
2500         isl_pw_aff *res;
2501
2502         is_cst = isl_pw_aff_is_cst(pa2);
2503         if (is_cst < 0)
2504                 goto error;
2505         if (!is_cst)
2506                 isl_die(isl_pw_aff_get_ctx(pa2), isl_error_invalid,
2507                         "second argument should be a piecewise constant",
2508                         goto error);
2509         res = isl_pw_aff_tdiv_q(isl_pw_aff_copy(pa1), isl_pw_aff_copy(pa2));
2510         res = isl_pw_aff_mul(pa2, res);
2511         res = isl_pw_aff_sub(pa1, res);
2512         return res;
2513 error:
2514         isl_pw_aff_free(pa1);
2515         isl_pw_aff_free(pa2);
2516         return NULL;
2517 }
2518
2519 static __isl_give isl_pw_aff *pw_aff_min(__isl_take isl_pw_aff *pwaff1,
2520         __isl_take isl_pw_aff *pwaff2)
2521 {
2522         isl_set *le;
2523         isl_set *dom;
2524
2525         dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1)),
2526                                 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2)));
2527         le = isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1),
2528                                 isl_pw_aff_copy(pwaff2));
2529         dom = isl_set_subtract(dom, isl_set_copy(le));
2530         return isl_pw_aff_select(le, pwaff1, dom, pwaff2);
2531 }
2532
2533 __isl_give isl_pw_aff *isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1,
2534         __isl_take isl_pw_aff *pwaff2)
2535 {
2536         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_min);
2537 }
2538
2539 static __isl_give isl_pw_aff *pw_aff_max(__isl_take isl_pw_aff *pwaff1,
2540         __isl_take isl_pw_aff *pwaff2)
2541 {
2542         isl_set *ge;
2543         isl_set *dom;
2544
2545         dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1)),
2546                                 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2)));
2547         ge = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1),
2548                                 isl_pw_aff_copy(pwaff2));
2549         dom = isl_set_subtract(dom, isl_set_copy(ge));
2550         return isl_pw_aff_select(ge, pwaff1, dom, pwaff2);
2551 }
2552
2553 __isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1,
2554         __isl_take isl_pw_aff *pwaff2)
2555 {
2556         return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_max);
2557 }
2558
2559 static __isl_give isl_pw_aff *pw_aff_list_reduce(
2560         __isl_take isl_pw_aff_list *list,
2561         __isl_give isl_pw_aff *(*fn)(__isl_take isl_pw_aff *pwaff1,
2562                                         __isl_take isl_pw_aff *pwaff2))
2563 {
2564         int i;
2565         isl_ctx *ctx;
2566         isl_pw_aff *res;
2567
2568         if (!list)
2569                 return NULL;
2570
2571         ctx = isl_pw_aff_list_get_ctx(list);
2572         if (list->n < 1)
2573                 isl_die(ctx, isl_error_invalid,
2574                         "list should contain at least one element",
2575                         return isl_pw_aff_list_free(list));
2576
2577         res = isl_pw_aff_copy(list->p[0]);
2578         for (i = 1; i < list->n; ++i)
2579                 res = fn(res, isl_pw_aff_copy(list->p[i]));
2580
2581         isl_pw_aff_list_free(list);
2582         return res;
2583 }
2584
2585 /* Return an isl_pw_aff that maps each element in the intersection of the
2586  * domains of the elements of list to the minimal corresponding affine
2587  * expression.
2588  */
2589 __isl_give isl_pw_aff *isl_pw_aff_list_min(__isl_take isl_pw_aff_list *list)
2590 {
2591         return pw_aff_list_reduce(list, &isl_pw_aff_min);
2592 }
2593
2594 /* Return an isl_pw_aff that maps each element in the intersection of the
2595  * domains of the elements of list to the maximal corresponding affine
2596  * expression.
2597  */
2598 __isl_give isl_pw_aff *isl_pw_aff_list_max(__isl_take isl_pw_aff_list *list)
2599 {
2600         return pw_aff_list_reduce(list, &isl_pw_aff_max);
2601 }
2602
2603 /* Mark the domains of "pwaff" as rational.
2604  */
2605 __isl_give isl_pw_aff *isl_pw_aff_set_rational(__isl_take isl_pw_aff *pwaff)
2606 {
2607         int i;
2608
2609         pwaff = isl_pw_aff_cow(pwaff);
2610         if (!pwaff)
2611                 return NULL;
2612         if (pwaff->n == 0)
2613                 return pwaff;
2614
2615         for (i = 0; i < pwaff->n; ++i) {
2616                 pwaff->p[i].set = isl_set_set_rational(pwaff->p[i].set);
2617                 if (!pwaff->p[i].set)
2618                         return isl_pw_aff_free(pwaff);
2619         }
2620
2621         return pwaff;
2622 }
2623
2624 /* Mark the domains of the elements of "list" as rational.
2625  */
2626 __isl_give isl_pw_aff_list *isl_pw_aff_list_set_rational(
2627         __isl_take isl_pw_aff_list *list)
2628 {
2629         int i, n;
2630
2631         if (!list)
2632                 return NULL;
2633         if (list->n == 0)
2634                 return list;
2635
2636         n = list->n;
2637         for (i = 0; i < n; ++i) {
2638                 isl_pw_aff *pa;
2639
2640                 pa = isl_pw_aff_list_get_pw_aff(list, i);
2641                 pa = isl_pw_aff_set_rational(pa);
2642                 list = isl_pw_aff_list_set_pw_aff(list, i, pa);
2643         }
2644
2645         return list;
2646 }
2647
2648 #undef BASE
2649 #define BASE aff
2650
2651 #include <isl_multi_templ.c>
2652
2653 /* Create an isl_pw_multi_aff with the given isl_multi_aff on a universe
2654  * domain.
2655  */
2656 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_multi_aff(
2657         __isl_take isl_multi_aff *ma)
2658 {
2659         isl_set *dom = isl_set_universe(isl_multi_aff_get_domain_space(ma));
2660         return isl_pw_multi_aff_alloc(dom, ma);
2661 }
2662
2663 /* Create a piecewise multi-affine expression in the given space that maps each
2664  * input dimension to the corresponding output dimension.
2665  */
2666 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_identity(
2667         __isl_take isl_space *space)
2668 {
2669         return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_identity(space));
2670 }
2671
2672 __isl_give isl_multi_aff *isl_multi_aff_add(__isl_take isl_multi_aff *maff1,
2673         __isl_take isl_multi_aff *maff2)
2674 {
2675         int i;
2676         isl_ctx *ctx;
2677
2678         maff1 = isl_multi_aff_cow(maff1);
2679         if (!maff1 || !maff2)
2680                 goto error;
2681
2682         ctx = isl_multi_aff_get_ctx(maff1);
2683         if (!isl_space_is_equal(maff1->space, maff2->space))
2684                 isl_die(ctx, isl_error_invalid,
2685                         "spaces don't match", goto error);
2686
2687         for (i = 0; i < maff1->n; ++i) {
2688                 maff1->p[i] = isl_aff_add(maff1->p[i],
2689                                             isl_aff_copy(maff2->p[i]));
2690                 if (!maff1->p[i])
2691                         goto error;
2692         }
2693
2694         isl_multi_aff_free(maff2);
2695         return maff1;
2696 error:
2697         isl_multi_aff_free(maff1);
2698         isl_multi_aff_free(maff2);
2699         return NULL;
2700 }
2701
2702 /* Given two multi-affine expressions A -> B and C -> D,
2703  * construct a multi-affine expression [A -> C] -> [B -> D].
2704  */
2705 __isl_give isl_multi_aff *isl_multi_aff_product(
2706         __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2)
2707 {
2708         int i;
2709         isl_aff *aff;
2710         isl_space *space;
2711         isl_multi_aff *res;
2712         int in1, in2, out1, out2;
2713
2714         in1 = isl_multi_aff_dim(ma1, isl_dim_in);
2715         in2 = isl_multi_aff_dim(ma2, isl_dim_in);
2716         out1 = isl_multi_aff_dim(ma1, isl_dim_out);
2717         out2 = isl_multi_aff_dim(ma2, isl_dim_out);
2718         space = isl_space_product(isl_multi_aff_get_space(ma1),
2719                                   isl_multi_aff_get_space(ma2));
2720         res = isl_multi_aff_alloc(isl_space_copy(space));
2721         space = isl_space_domain(space);
2722
2723         for (i = 0; i < out1; ++i) {
2724                 aff = isl_multi_aff_get_aff(ma1, i);
2725                 aff = isl_aff_insert_dims(aff, isl_dim_in, in1, in2);
2726                 aff = isl_aff_reset_domain_space(aff, isl_space_copy(space));
2727                 res = isl_multi_aff_set_aff(res, i, aff);
2728         }
2729
2730         for (i = 0; i < out2; ++i) {
2731                 aff = isl_multi_aff_get_aff(ma2, i);
2732                 aff = isl_aff_insert_dims(aff, isl_dim_in, 0, in1);
2733                 aff = isl_aff_reset_domain_space(aff, isl_space_copy(space));
2734                 res = isl_multi_aff_set_aff(res, out1 + i, aff);
2735         }
2736
2737         isl_space_free(space);
2738         isl_multi_aff_free(ma1);
2739         isl_multi_aff_free(ma2);
2740         return res;
2741 }
2742
2743 /* Exploit the equalities in "eq" to simplify the affine expressions.
2744  */
2745 static __isl_give isl_multi_aff *isl_multi_aff_substitute_equalities(
2746         __isl_take isl_multi_aff *maff, __isl_take isl_basic_set *eq)
2747 {
2748         int i;
2749
2750         maff = isl_multi_aff_cow(maff);
2751         if (!maff || !eq)
2752                 goto error;
2753
2754         for (i = 0; i < maff->n; ++i) {
2755                 maff->p[i] = isl_aff_substitute_equalities(maff->p[i],
2756                                                     isl_basic_set_copy(eq));
2757                 if (!maff->p[i])
2758                         goto error;
2759         }
2760
2761         isl_basic_set_free(eq);
2762         return maff;
2763 error:
2764         isl_basic_set_free(eq);
2765         isl_multi_aff_free(maff);
2766         return NULL;
2767 }
2768
2769 __isl_give isl_multi_aff *isl_multi_aff_scale(__isl_take isl_multi_aff *maff,
2770         isl_int f)
2771 {
2772         int i;
2773
2774         maff = isl_multi_aff_cow(maff);
2775         if (!maff)
2776                 return NULL;
2777
2778         for (i = 0; i < maff->n; ++i) {
2779                 maff->p[i] = isl_aff_scale(maff->p[i], f);
2780                 if (!maff->p[i])
2781                         return isl_multi_aff_free(maff);
2782         }
2783
2784         return maff;
2785 }
2786
2787 __isl_give isl_multi_aff *isl_multi_aff_add_on_domain(__isl_keep isl_set *dom,
2788         __isl_take isl_multi_aff *maff1, __isl_take isl_multi_aff *maff2)
2789 {
2790         maff1 = isl_multi_aff_add(maff1, maff2);
2791         maff1 = isl_multi_aff_gist(maff1, isl_set_copy(dom));
2792         return maff1;
2793 }
2794
2795 int isl_multi_aff_is_empty(__isl_keep isl_multi_aff *maff)
2796 {
2797         if (!maff)
2798                 return -1;
2799
2800         return 0;
2801 }
2802
2803 int isl_multi_aff_plain_is_equal(__isl_keep isl_multi_aff *maff1,
2804         __isl_keep isl_multi_aff *maff2)
2805 {
2806         int i;
2807         int equal;
2808
2809         if (!maff1 || !maff2)
2810                 return -1;
2811         if (maff1->n != maff2->n)
2812                 return 0;
2813         equal = isl_space_is_equal(maff1->space, maff2->space);
2814         if (equal < 0 || !equal)
2815                 return equal;
2816
2817         for (i = 0; i < maff1->n; ++i) {
2818                 equal = isl_aff_plain_is_equal(maff1->p[i], maff2->p[i]);
2819                 if (equal < 0 || !equal)
2820                         return equal;
2821         }
2822
2823         return 1;
2824 }
2825
2826 /* Return the set of domain elements where "ma1" is lexicographically
2827  * smaller than or equal to "ma2".
2828  */
2829 __isl_give isl_set *isl_multi_aff_lex_le_set(__isl_take isl_multi_aff *ma1,
2830         __isl_take isl_multi_aff *ma2)
2831 {
2832         return isl_multi_aff_lex_ge_set(ma2, ma1);
2833 }
2834
2835 /* Return the set of domain elements where "ma1" is lexicographically
2836  * greater than or equal to "ma2".
2837  */
2838 __isl_give isl_set *isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff *ma1,
2839         __isl_take isl_multi_aff *ma2)
2840 {
2841         isl_space *space;
2842         isl_map *map1, *map2;
2843         isl_map *map, *ge;
2844
2845         map1 = isl_map_from_multi_aff(ma1);
2846         map2 = isl_map_from_multi_aff(ma2);
2847         map = isl_map_range_product(map1, map2);
2848         space = isl_space_range(isl_map_get_space(map));
2849         space = isl_space_domain(isl_space_unwrap(space));
2850         ge = isl_map_lex_ge(space);
2851         map = isl_map_intersect_range(map, isl_map_wrap(ge));
2852
2853         return isl_map_domain(map);
2854 }
2855
2856 #undef PW
2857 #define PW isl_pw_multi_aff
2858 #undef EL
2859 #define EL isl_multi_aff
2860 #undef EL_IS_ZERO
2861 #define EL_IS_ZERO is_empty
2862 #undef ZERO
2863 #define ZERO empty
2864 #undef IS_ZERO
2865 #define IS_ZERO is_empty
2866 #undef FIELD
2867 #define FIELD maff
2868 #undef DEFAULT_IS_ZERO
2869 #define DEFAULT_IS_ZERO 0
2870
2871 #define NO_NEG
2872 #define NO_EVAL
2873 #define NO_OPT
2874 #define NO_INVOLVES_DIMS
2875 #define NO_MOVE_DIMS
2876 #define NO_INSERT_DIMS
2877 #define NO_LIFT
2878 #define NO_MORPH
2879
2880 #include <isl_pw_templ.c>
2881
2882 #undef UNION
2883 #define UNION isl_union_pw_multi_aff
2884 #undef PART
2885 #define PART isl_pw_multi_aff
2886 #undef PARTS
2887 #define PARTS pw_multi_aff
2888 #define ALIGN_DOMAIN
2889
2890 #define NO_EVAL
2891
2892 #include <isl_union_templ.c>
2893
2894 /* Given a function "cmp" that returns the set of elements where
2895  * "ma1" is "better" than "ma2", return the intersection of this
2896  * set with "dom1" and "dom2".
2897  */
2898 static __isl_give isl_set *shared_and_better(__isl_keep isl_set *dom1,
2899         __isl_keep isl_set *dom2, __isl_keep isl_multi_aff *ma1,
2900         __isl_keep isl_multi_aff *ma2,
2901         __isl_give isl_set *(*cmp)(__isl_take isl_multi_aff *ma1,
2902                                     __isl_take isl_multi_aff *ma2))
2903 {
2904         isl_set *common;
2905         isl_set *better;
2906         int is_empty;
2907
2908         common = isl_set_intersect(isl_set_copy(dom1), isl_set_copy(dom2));
2909         is_empty = isl_set_plain_is_empty(common);
2910         if (is_empty >= 0 && is_empty)
2911                 return common;
2912         if (is_empty < 0)
2913                 return isl_set_free(common);
2914         better = cmp(isl_multi_aff_copy(ma1), isl_multi_aff_copy(ma2));
2915         better = isl_set_intersect(common, better);
2916
2917         return better;
2918 }
2919
2920 /* Given a function "cmp" that returns the set of elements where
2921  * "ma1" is "better" than "ma2", return a piecewise multi affine
2922  * expression defined on the union of the definition domains
2923  * of "pma1" and "pma2" that maps to the "best" of "pma1" and
2924  * "pma2" on each cell.  If only one of the two input functions
2925  * is defined on a given cell, then it is considered the best.
2926  */
2927 static __isl_give isl_pw_multi_aff *pw_multi_aff_union_opt(
2928         __isl_take isl_pw_multi_aff *pma1,
2929         __isl_take isl_pw_multi_aff *pma2,
2930         __isl_give isl_set *(*cmp)(__isl_take isl_multi_aff *ma1,
2931                                     __isl_take isl_multi_aff *ma2))
2932 {
2933         int i, j, n;
2934         isl_pw_multi_aff *res = NULL;
2935         isl_ctx *ctx;
2936         isl_set *set = NULL;
2937
2938         if (!pma1 || !pma2)
2939                 goto error;
2940
2941         ctx = isl_space_get_ctx(pma1->dim);
2942         if (!isl_space_is_equal(pma1->dim, pma2->dim))
2943                 isl_die(ctx, isl_error_invalid,
2944                         "arguments should live in the same space", goto error);
2945
2946         if (isl_pw_multi_aff_is_empty(pma1)) {
2947                 isl_pw_multi_aff_free(pma1);
2948                 return pma2;
2949         }
2950
2951         if (isl_pw_multi_aff_is_empty(pma2)) {
2952                 isl_pw_multi_aff_free(pma2);
2953                 return pma1;
2954         }
2955
2956         n = 2 * (pma1->n + 1) * (pma2->n + 1);
2957         res = isl_pw_multi_aff_alloc_size(isl_space_copy(pma1->dim), n);
2958
2959         for (i = 0; i < pma1->n; ++i) {
2960                 set = isl_set_copy(pma1->p[i].set);
2961                 for (j = 0; j < pma2->n; ++j) {
2962                         isl_set *better;
2963                         int is_empty;
2964
2965                         better = shared_and_better(pma2->p[j].set,
2966                                         pma1->p[i].set, pma2->p[j].maff,
2967                                         pma1->p[i].maff, cmp);
2968                         is_empty = isl_set_plain_is_empty(better);
2969                         if (is_empty < 0 || is_empty) {
2970                                 isl_set_free(better);
2971                                 if (is_empty < 0)
2972                                         goto error;
2973                                 continue;
2974                         }
2975                         set = isl_set_subtract(set, isl_set_copy(better));
2976
2977                         res = isl_pw_multi_aff_add_piece(res, better,
2978                                         isl_multi_aff_copy(pma2->p[j].maff));
2979                 }
2980                 res = isl_pw_multi_aff_add_piece(res, set,
2981                                         isl_multi_aff_copy(pma1->p[i].maff));
2982         }
2983
2984         for (j = 0; j < pma2->n; ++j) {
2985                 set = isl_set_copy(pma2->p[j].set);
2986                 for (i = 0; i < pma1->n; ++i)
2987                         set = isl_set_subtract(set,
2988                                         isl_set_copy(pma1->p[i].set));
2989                 res = isl_pw_multi_aff_add_piece(res, set,
2990                                         isl_multi_aff_copy(pma2->p[j].maff));
2991         }
2992
2993         isl_pw_multi_aff_free(pma1);
2994         isl_pw_multi_aff_free(pma2);
2995
2996         return res;
2997 error:
2998         isl_pw_multi_aff_free(pma1);
2999         isl_pw_multi_aff_free(pma2);
3000         isl_set_free(set);
3001         return isl_pw_multi_aff_free(res);
3002 }
3003
3004 static __isl_give isl_pw_multi_aff *pw_multi_aff_union_lexmax(
3005         __isl_take isl_pw_multi_aff *pma1,
3006         __isl_take isl_pw_multi_aff *pma2)
3007 {
3008         return pw_multi_aff_union_opt(pma1, pma2, &isl_multi_aff_lex_ge_set);
3009 }
3010
3011 /* Given two piecewise multi affine expressions, return a piecewise
3012  * multi-affine expression defined on the union of the definition domains
3013  * of the inputs that is equal to the lexicographic maximum of the two
3014  * inputs on each cell.  If only one of the two inputs is defined on
3015  * a given cell, then it is considered to be the maximum.
3016  */
3017 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_lexmax(
3018         __isl_take isl_pw_multi_aff *pma1,
3019         __isl_take isl_pw_multi_aff *pma2)
3020 {
3021         return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
3022                                                     &pw_multi_aff_union_lexmax);
3023 }
3024
3025 static __isl_give isl_pw_multi_aff *pw_multi_aff_union_lexmin(
3026         __isl_take isl_pw_multi_aff *pma1,
3027         __isl_take isl_pw_multi_aff *pma2)
3028 {
3029         return pw_multi_aff_union_opt(pma1, pma2, &isl_multi_aff_lex_le_set);
3030 }
3031
3032 /* Given two piecewise multi affine expressions, return a piecewise
3033  * multi-affine expression defined on the union of the definition domains
3034  * of the inputs that is equal to the lexicographic minimum of the two
3035  * inputs on each cell.  If only one of the two inputs is defined on
3036  * a given cell, then it is considered to be the minimum.
3037  */
3038 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_lexmin(
3039         __isl_take isl_pw_multi_aff *pma1,
3040         __isl_take isl_pw_multi_aff *pma2)
3041 {
3042         return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
3043                                                     &pw_multi_aff_union_lexmin);
3044 }
3045
3046 static __isl_give isl_pw_multi_aff *pw_multi_aff_add(
3047         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
3048 {
3049         return isl_pw_multi_aff_on_shared_domain(pma1, pma2,
3050                                                 &isl_multi_aff_add);
3051 }
3052
3053 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_add(
3054         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
3055 {
3056         return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
3057                                                 &pw_multi_aff_add);
3058 }
3059
3060 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_add(
3061         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
3062 {
3063         return isl_pw_multi_aff_union_add_(pma1, pma2);
3064 }
3065
3066 /* Given two piecewise multi-affine expressions A -> B and C -> D,
3067  * construct a piecewise multi-affine expression [A -> C] -> [B -> D].
3068  */
3069 static __isl_give isl_pw_multi_aff *pw_multi_aff_product(
3070         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
3071 {
3072         int i, j, n;
3073         isl_space *space;
3074         isl_pw_multi_aff *res;
3075
3076         if (!pma1 || !pma2)
3077                 goto error;
3078
3079         n = pma1->n * pma2->n;
3080         space = isl_space_product(isl_space_copy(pma1->dim),
3081                                   isl_space_copy(pma2->dim));
3082         res = isl_pw_multi_aff_alloc_size(space, n);
3083
3084         for (i = 0; i < pma1->n; ++i) {
3085                 for (j = 0; j < pma2->n; ++j) {
3086                         isl_set *domain;
3087                         isl_multi_aff *ma;
3088
3089                         domain = isl_set_product(isl_set_copy(pma1->p[i].set),
3090                                                  isl_set_copy(pma2->p[j].set));
3091                         ma = isl_multi_aff_product(
3092                                         isl_multi_aff_copy(pma1->p[i].maff),
3093                                         isl_multi_aff_copy(pma2->p[i].maff));
3094                         res = isl_pw_multi_aff_add_piece(res, domain, ma);
3095                 }
3096         }
3097
3098         isl_pw_multi_aff_free(pma1);
3099         isl_pw_multi_aff_free(pma2);
3100         return res;
3101 error:
3102         isl_pw_multi_aff_free(pma1);
3103         isl_pw_multi_aff_free(pma2);
3104         return NULL;
3105 }
3106
3107 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_product(
3108         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
3109 {
3110         return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
3111                                                 &pw_multi_aff_product);
3112 }
3113
3114 /* Construct a map mapping the domain of the piecewise multi-affine expression
3115  * to its range, with each dimension in the range equated to the
3116  * corresponding affine expression on its cell.
3117  */
3118 __isl_give isl_map *isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
3119 {
3120         int i;
3121         isl_map *map;
3122
3123         if (!pma)
3124                 return NULL;
3125
3126         map = isl_map_empty(isl_pw_multi_aff_get_space(pma));
3127
3128         for (i = 0; i < pma->n; ++i) {
3129                 isl_multi_aff *maff;
3130                 isl_basic_map *bmap;
3131                 isl_map *map_i;
3132
3133                 maff = isl_multi_aff_copy(pma->p[i].maff);
3134                 bmap = isl_basic_map_from_multi_aff(maff);
3135                 map_i = isl_map_from_basic_map(bmap);
3136                 map_i = isl_map_intersect_domain(map_i,
3137                                                 isl_set_copy(pma->p[i].set));
3138                 map = isl_map_union_disjoint(map, map_i);
3139         }
3140
3141         isl_pw_multi_aff_free(pma);
3142         return map;
3143 }
3144
3145 __isl_give isl_set *isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
3146 {
3147         if (!pma)
3148                 return NULL;
3149
3150         if (!isl_space_is_set(pma->dim))
3151                 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
3152                         "isl_pw_multi_aff cannot be converted into an isl_set",
3153                         return isl_pw_multi_aff_free(pma));
3154
3155         return isl_map_from_pw_multi_aff(pma);
3156 }
3157
3158 /* Given a basic map with a single output dimension that is defined
3159  * in terms of the parameters and input dimensions using an equality,
3160  * extract an isl_aff that expresses the output dimension in terms
3161  * of the parameters and input dimensions.
3162  *
3163  * Since some applications expect the result of isl_pw_multi_aff_from_map
3164  * to only contain integer affine expressions, we compute the floor
3165  * of the expression before returning.
3166  *
3167  * This function shares some similarities with
3168  * isl_basic_map_has_defining_equality and isl_constraint_get_bound.
3169  */
3170 static __isl_give isl_aff *extract_isl_aff_from_basic_map(
3171         __isl_take isl_basic_map *bmap)
3172 {
3173         int i;
3174         unsigned offset;
3175         unsigned total;
3176         isl_local_space *ls;
3177         isl_aff *aff;
3178
3179         if (!bmap)
3180                 return NULL;
3181         if (isl_basic_map_dim(bmap, isl_dim_out) != 1)
3182                 isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
3183                         "basic map should have a single output dimension",
3184                         goto error);
3185         offset = isl_basic_map_offset(bmap, isl_dim_out);
3186         total = isl_basic_map_total_dim(bmap);
3187         for (i = 0; i < bmap->n_eq; ++i) {
3188                 if (isl_int_is_zero(bmap->eq[i][offset]))
3189                         continue;
3190                 if (isl_seq_first_non_zero(bmap->eq[i] + offset + 1,
3191                                            1 + total - (offset + 1)) != -1)
3192                         continue;
3193                 break;
3194         }
3195         if (i >= bmap->n_eq)
3196                 isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
3197                         "unable to find suitable equality", goto error);
3198         ls = isl_basic_map_get_local_space(bmap);
3199         aff = isl_aff_alloc(isl_local_space_domain(ls));
3200         if (!aff)
3201                 goto error;
3202         if (isl_int_is_neg(bmap->eq[i][offset]))
3203                 isl_seq_cpy(aff->v->el + 1, bmap->eq[i], offset);
3204         else
3205                 isl_seq_neg(aff->v->el + 1, bmap->eq[i], offset);
3206         isl_seq_clr(aff->v->el + 1 + offset, aff->v->size - (1 + offset));
3207         isl_int_abs(aff->v->el[0], bmap->eq[i][offset]);
3208         isl_basic_map_free(bmap);
3209
3210         aff = isl_aff_remove_unused_divs(aff);
3211         aff = isl_aff_floor(aff);
3212         return aff;
3213 error:
3214         isl_basic_map_free(bmap);
3215         return NULL;
3216 }
3217
3218 /* Given a basic map where each output dimension is defined
3219  * in terms of the parameters and input dimensions using an equality,
3220  * extract an isl_multi_aff that expresses the output dimensions in terms
3221  * of the parameters and input dimensions.
3222  */
3223 static __isl_give isl_multi_aff *extract_isl_multi_aff_from_basic_map(
3224         __isl_take isl_basic_map *bmap)
3225 {
3226         int i;
3227         unsigned n_out;
3228         isl_multi_aff *ma;
3229
3230         if (!bmap)
3231                 return NULL;
3232
3233         ma = isl_multi_aff_alloc(isl_basic_map_get_space(bmap));
3234         n_out = isl_basic_map_dim(bmap, isl_dim_out);
3235
3236         for (i = 0; i < n_out; ++i) {
3237                 isl_basic_map *bmap_i;
3238                 isl_aff *aff;
3239
3240                 bmap_i = isl_basic_map_copy(bmap);
3241                 bmap_i = isl_basic_map_project_out(bmap_i, isl_dim_out,
3242                                                         i + 1, n_out - (1 + i));
3243                 bmap_i = isl_basic_map_project_out(bmap_i, isl_dim_out, 0, i);
3244                 aff = extract_isl_aff_from_basic_map(bmap_i);
3245                 ma = isl_multi_aff_set_aff(ma, i, aff);
3246         }
3247
3248         isl_basic_map_free(bmap);
3249
3250         return ma;
3251 }
3252
3253 /* Create an isl_pw_multi_aff that is equivalent to
3254  * isl_map_intersect_domain(isl_map_from_basic_map(bmap), domain).
3255  * The given basic map is such that each output dimension is defined
3256  * in terms of the parameters and input dimensions using an equality.
3257  */
3258 static __isl_give isl_pw_multi_aff *plain_pw_multi_aff_from_map(
3259         __isl_take isl_set *domain, __isl_take isl_basic_map *bmap)
3260 {
3261         isl_multi_aff *ma;
3262
3263         ma = extract_isl_multi_aff_from_basic_map(bmap);
3264         return isl_pw_multi_aff_alloc(domain, ma);
3265 }
3266
3267 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
3268  * This obviously only works if the input "map" is single-valued.
3269  * If so, we compute the lexicographic minimum of the image in the form
3270  * of an isl_pw_multi_aff.  Since the image is unique, it is equal
3271  * to its lexicographic minimum.
3272  * If the input is not single-valued, we produce an error.
3273  */
3274 static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_base(
3275         __isl_take isl_map *map)
3276 {
3277         int i;
3278         int sv;
3279         isl_pw_multi_aff *pma;
3280
3281         sv = isl_map_is_single_valued(map);
3282         if (sv < 0)
3283                 goto error;
3284         if (!sv)
3285                 isl_die(isl_map_get_ctx(map), isl_error_invalid,
3286                         "map is not single-valued", goto error);
3287         map = isl_map_make_disjoint(map);
3288         if (!map)
3289                 return NULL;
3290
3291         pma = isl_pw_multi_aff_empty(isl_map_get_space(map));
3292
3293         for (i = 0; i < map->n; ++i) {
3294                 isl_pw_multi_aff *pma_i;
3295                 isl_basic_map *bmap;
3296                 bmap = isl_basic_map_copy(map->p[i]);
3297                 pma_i = isl_basic_map_lexmin_pw_multi_aff(bmap);
3298                 pma = isl_pw_multi_aff_add_disjoint(pma, pma_i);
3299         }
3300
3301         isl_map_free(map);
3302         return pma;
3303 error:
3304         isl_map_free(map);
3305         return NULL;
3306 }
3307
3308 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
3309  * taking into account that the output dimension at position "d"
3310  * can be represented as
3311  *
3312  *      x = floor((e(...) + c1) / m)
3313  *
3314  * given that constraint "i" is of the form
3315  *
3316  *      e(...) + c1 - m x >= 0
3317  *
3318  *
3319  * Let "map" be of the form
3320  *
3321  *      A -> B
3322  *
3323  * We construct a mapping
3324  *
3325  *      A -> [A -> x = floor(...)]
3326  *
3327  * apply that to the map, obtaining
3328  *
3329  *      [A -> x = floor(...)] -> B
3330  *
3331  * and equate dimension "d" to x.
3332  * We then compute a isl_pw_multi_aff representation of the resulting map
3333  * and plug in the mapping above.
3334  */
3335 static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_div(
3336         __isl_take isl_map *map, __isl_take isl_basic_map *hull, int d, int i)
3337 {
3338         isl_ctx *ctx;
3339         isl_space *space;
3340         isl_local_space *ls;
3341         isl_multi_aff *ma;
3342         isl_aff *aff;
3343         isl_vec *v;
3344         isl_map *insert;
3345         int offset;
3346         int n;
3347         int n_in;
3348         isl_pw_multi_aff *pma;
3349         int is_set;
3350
3351         is_set = isl_map_is_set(map);
3352
3353         offset = isl_basic_map_offset(hull, isl_dim_out);
3354         ctx = isl_map_get_ctx(map);
3355         space = isl_space_domain(isl_map_get_space(map));
3356         n_in = isl_space_dim(space, isl_dim_set);
3357         n = isl_space_dim(space, isl_dim_all);
3358
3359         v = isl_vec_alloc(ctx, 1 + 1 + n);
3360         if (v) {
3361                 isl_int_neg(v->el[0], hull->ineq[i][offset + d]);
3362                 isl_seq_cpy(v->el + 1, hull->ineq[i], 1 + n);
3363         }
3364         isl_basic_map_free(hull);
3365
3366         ls = isl_local_space_from_space(isl_space_copy(space));
3367         aff = isl_aff_alloc_vec(ls, v);
3368         aff = isl_aff_floor(aff);
3369         if (is_set) {
3370                 isl_space_free(space);
3371                 ma = isl_multi_aff_from_aff(aff);
3372         } else {
3373                 ma = isl_multi_aff_identity(isl_space_map_from_set(space));
3374                 ma = isl_multi_aff_range_product(ma,
3375                                                 isl_multi_aff_from_aff(aff));
3376         }
3377
3378         insert = isl_map_from_multi_aff(isl_multi_aff_copy(ma));
3379         map = isl_map_apply_domain(map, insert);
3380         map = isl_map_equate(map, isl_dim_in, n_in, isl_dim_out, d);
3381         pma = isl_pw_multi_aff_from_map(map);
3382         pma = isl_pw_multi_aff_pullback_multi_aff(pma, ma);
3383
3384         return pma;
3385 }
3386
3387 /* Is constraint "c" of the form
3388  *
3389  *      e(...) + c1 - m x >= 0
3390  *
3391  * or
3392  *
3393  *      -e(...) + c2 + m x >= 0
3394  *
3395  * where m > 1 and e only depends on parameters and input dimemnsions?
3396  *
3397  * "offset" is the offset of the output dimensions
3398  * "pos" is the position of output dimension x.
3399  */
3400 static int is_potential_div_constraint(isl_int *c, int offset, int d, int total)
3401 {
3402         if (isl_int_is_zero(c[offset + d]))
3403                 return 0;
3404         if (isl_int_is_one(c[offset + d]))
3405                 return 0;
3406         if (isl_int_is_negone(c[offset + d]))
3407                 return 0;
3408         if (isl_seq_first_non_zero(c + offset, d) != -1)
3409                 return 0;
3410         if (isl_seq_first_non_zero(c + offset + d + 1,
3411                                     total - (offset + d + 1)) != -1)
3412                 return 0;
3413         return 1;
3414 }
3415
3416 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
3417  *
3418  * As a special case, we first check if there is any pair of constraints,
3419  * shared by all the basic maps in "map" that force a given dimension
3420  * to be equal to the floor of some affine combination of the input dimensions.
3421  *
3422  * In particular, if we can find two constraints
3423  *
3424  *      e(...) + c1 - m x >= 0          i.e.,           m x <= e(...) + c1
3425  *
3426  * and
3427  *
3428  *      -e(...) + c2 + m x >= 0         i.e.,           m x >= e(...) - c2
3429  *
3430  * where m > 1 and e only depends on parameters and input dimemnsions,
3431  * and such that
3432  *
3433  *      c1 + c2 < m                     i.e.,           -c2 >= c1 - (m - 1)
3434  *
3435  * then we know that we can take
3436  *
3437  *      x = floor((e(...) + c1) / m)
3438  *
3439  * without having to perform any computation.
3440  *
3441  * Note that we know that
3442  *
3443  *      c1 + c2 >= 1
3444  *
3445  * If c1 + c2 were 0, then we would have detected an equality during
3446  * simplification.  If c1 + c2 were negative, then we would have detected
3447  * a contradiction.
3448  */
3449 static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_check_div(
3450         __isl_take isl_map *map)
3451 {
3452         int d, dim;
3453         int i, j, n;
3454         int offset, total;
3455         isl_int sum;
3456         isl_basic_map *hull;
3457
3458         hull = isl_map_unshifted_simple_hull(isl_map_copy(map));
3459         if (!hull)
3460                 goto error;
3461
3462         isl_int_init(sum);
3463         dim = isl_map_dim(map, isl_dim_out);
3464         offset = isl_basic_map_offset(hull, isl_dim_out);
3465         total = 1 + isl_basic_map_total_dim(hull);
3466         n = hull->n_ineq;
3467         for (d = 0; d < dim; ++d) {
3468                 for (i = 0; i < n; ++i) {
3469                         if (!is_potential_div_constraint(hull->ineq[i],
3470                                                         offset, d, total))
3471                                 continue;
3472                         for (j = i + 1; j < n; ++j) {
3473                                 if (!isl_seq_is_neg(hull->ineq[i] + 1,
3474                                                 hull->ineq[j] + 1, total - 1))
3475                                         continue;
3476                                 isl_int_add(sum, hull->ineq[i][0],
3477                                                 hull->ineq[j][0]);
3478                                 if (isl_int_abs_lt(sum,
3479                                                     hull->ineq[i][offset + d]))
3480                                         break;
3481
3482                         }
3483                         if (j >= n)
3484                                 continue;
3485                         isl_int_clear(sum);
3486                         if (isl_int_is_pos(hull->ineq[j][offset + d]))
3487                                 j = i;
3488                         return pw_multi_aff_from_map_div(map, hull, d, j);
3489                 }
3490         }
3491         isl_int_clear(sum);
3492         isl_basic_map_free(hull);
3493         return pw_multi_aff_from_map_base(map);
3494 error:
3495         isl_map_free(map);
3496         isl_basic_map_free(hull);
3497         return NULL;
3498 }
3499
3500 /* Given an affine expression
3501  *
3502  *      [A -> B] -> f(A,B)
3503  *
3504  * construct an isl_multi_aff
3505  *
3506  *      [A -> B] -> B'
3507  *
3508  * such that dimension "d" in B' is set to "aff" and the remaining
3509  * dimensions are set equal to the corresponding dimensions in B.
3510  * "n_in" is the dimension of the space A.
3511  * "n_out" is the dimension of the space B.
3512  *
3513  * If "is_set" is set, then the affine expression is of the form
3514  *
3515  *      [B] -> f(B)
3516  *
3517  * and we construct an isl_multi_aff
3518  *
3519  *      B -> B'
3520  */
3521 static __isl_give isl_multi_aff *range_map(__isl_take isl_aff *aff, int d,
3522         unsigned n_in, unsigned n_out, int is_set)
3523 {
3524         int i;
3525         isl_multi_aff *ma;
3526         isl_space *space, *space2;
3527         isl_local_space *ls;
3528
3529         space = isl_aff_get_domain_space(aff);
3530         ls = isl_local_space_from_space(isl_space_copy(space));
3531         space2 = isl_space_copy(space);
3532         if (!is_set)
3533                 space2 = isl_space_range(isl_space_unwrap(space2));
3534         space = isl_space_map_from_domain_and_range(space, space2);
3535         ma = isl_multi_aff_alloc(space);
3536         ma = isl_multi_aff_set_aff(ma, d, aff);
3537
3538         for (i = 0; i < n_out; ++i) {
3539                 if (i == d)
3540                         continue;
3541                 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
3542                                                 isl_dim_set, n_in + i);
3543                 ma = isl_multi_aff_set_aff(ma, i, aff);
3544         }
3545
3546         isl_local_space_free(ls);
3547
3548         return ma;
3549 }
3550
3551 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
3552  * taking into account that the dimension at position "d" can be written as
3553  *
3554  *      x = m a + f(..)                                         (1)
3555  *
3556  * where m is equal to "gcd".
3557  * "i" is the index of the equality in "hull" that defines f(..).
3558  * In particular, the equality is of the form
3559  *
3560  *      f(..) - x + m g(existentials) = 0
3561  *
3562  * or
3563  *
3564  *      -f(..) + x + m g(existentials) = 0
3565  *
3566  * We basically plug (1) into "map", resulting in a map with "a"
3567  * in the range instead of "x".  The corresponding isl_pw_multi_aff
3568  * defining "a" is then plugged back into (1) to obtain a definition fro "x".
3569  *
3570  * Specifically, given the input map
3571  *
3572  *      A -> B
3573  *
3574  * We first wrap it into a set
3575  *
3576  *      [A -> B]
3577  *
3578  * and define (1) on top of the corresponding space, resulting in "aff".
3579  * We use this to create an isl_multi_aff that maps the output position "d"
3580  * from "a" to "x", leaving all other (intput and output) dimensions unchanged.
3581  * We plug this into the wrapped map, unwrap the result and compute the
3582  * corresponding isl_pw_multi_aff.
3583  * The result is an expression
3584  *
3585  *      A -> T(A)
3586  *
3587  * We adjust that to
3588  *
3589  *      A -> [A -> T(A)]
3590  *
3591  * so that we can plug that into "aff", after extending the latter to
3592  * a mapping
3593  *
3594  *      [A -> B] -> B'
3595  *
3596  *
3597  * If "map" is actually a set, then there is no "A" space, meaning
3598  * that we do not need to perform any wrapping, and that the result
3599  * of the recursive call is of the form
3600  *
3601  *      [T]
3602  *
3603  * which is plugged into a mapping of the form
3604  *
3605  *      B -> B'
3606  */
3607 static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_stride(
3608         __isl_take isl_map *map, __isl_take isl_basic_map *hull, int d, int i,
3609         isl_int gcd)
3610 {
3611         isl_set *set;
3612         isl_space *space;
3613         isl_local_space *ls;
3614         isl_aff *aff;
3615         isl_multi_aff *ma;
3616         isl_pw_multi_aff *pma, *id;
3617         unsigned n_in;
3618         unsigned o_out;
3619         unsigned n_out;
3620         int is_set;
3621
3622         is_set = isl_map_is_set(map);
3623
3624         n_in = isl_basic_map_dim(hull, isl_dim_in);
3625         n_out = isl_basic_map_dim(hull, isl_dim_out);
3626         o_out = isl_basic_map_offset(hull, isl_dim_out);
3627
3628         if (is_set)
3629                 set = map;
3630         else
3631                 set = isl_map_wrap(map);
3632         space = isl_space_map_from_set(isl_set_get_space(set));
3633         ma = isl_multi_aff_identity(space);
3634         ls = isl_local_space_from_space(isl_set_get_space(set));
3635         aff = isl_aff_alloc(ls);
3636         if (aff) {
3637                 isl_int_set_si(aff->v->el[0], 1);
3638                 if (isl_int_is_one(hull->eq[i][o_out + d]))
3639                         isl_seq_neg(aff->v->el + 1, hull->eq[i],
3640                                     aff->v->size - 1);
3641                 else
3642                         isl_seq_cpy(aff->v->el + 1, hull->eq[i],
3643                                     aff->v->size - 1);
3644                 isl_int_set(aff->v->el[1 + o_out + d], gcd);
3645         }
3646         ma = isl_multi_aff_set_aff(ma, n_in + d, isl_aff_copy(aff));
3647         set = isl_set_preimage_multi_aff(set, ma);
3648
3649         ma = range_map(aff, d, n_in, n_out, is_set);
3650
3651         if (is_set)
3652                 map = set;
3653         else
3654                 map = isl_set_unwrap(set);
3655         pma = isl_pw_multi_aff_from_map(set);
3656
3657         if (!is_set) {
3658                 space = isl_pw_multi_aff_get_domain_space(pma);
3659                 space = isl_space_map_from_set(space);
3660                 id = isl_pw_multi_aff_identity(space);
3661                 pma = isl_pw_multi_aff_range_product(id, pma);
3662         }
3663         id = isl_pw_multi_aff_from_multi_aff(ma);
3664         pma = isl_pw_multi_aff_pullback_pw_multi_aff(id, pma);
3665
3666         isl_basic_map_free(hull);
3667         return pma;
3668 }
3669
3670 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
3671  *
3672  * As a special case, we first check if all output dimensions are uniquely
3673  * defined in terms of the parameters and input dimensions over the entire
3674  * domain.  If so, we extract the desired isl_pw_multi_aff directly
3675  * from the affine hull of "map" and its domain.
3676  *
3677  * Otherwise, we check if any of the output dimensions is "strided".
3678  * That is, we check if can be written as
3679  *
3680  *      x = m a + f(..)
3681  *
3682  * with m greater than 1, a some combination of existentiall quantified
3683  * variables and f and expression in the parameters and input dimensions.
3684  * If so, we remove the stride in pw_multi_aff_from_map_stride.
3685  *
3686  * Otherwise, we continue with pw_multi_aff_from_map_check_div for a further
3687  * special case.
3688  */
3689 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_map(__isl_take isl_map *map)
3690 {
3691         int i, j;
3692         int sv;
3693         isl_basic_map *hull;
3694         unsigned n_out;
3695         unsigned o_out;
3696         unsigned n_div;
3697         unsigned o_div;
3698         isl_int gcd;
3699
3700         if (!map)
3701                 return NULL;
3702
3703         hull = isl_map_affine_hull(isl_map_copy(map));
3704         sv = isl_basic_map_plain_is_single_valued(hull);
3705         if (sv >= 0 && sv)
3706                 return plain_pw_multi_aff_from_map(isl_map_domain(map), hull);
3707         if (sv < 0)
3708                 hull = isl_basic_map_free(hull);
3709         if (!hull)
3710                 goto error;
3711
3712         n_div = isl_basic_map_dim(hull, isl_dim_div);
3713         o_div = isl_basic_map_offset(hull, isl_dim_div);
3714
3715         if (n_div == 0) {
3716                 isl_basic_map_free(hull);
3717                 return pw_multi_aff_from_map_check_div(map);
3718         }
3719
3720         isl_int_init(gcd);
3721
3722         n_out = isl_basic_map_dim(hull, isl_dim_out);
3723         o_out = isl_basic_map_offset(hull, isl_dim_out);
3724
3725         for (i = 0; i < n_out; ++i) {
3726                 for (j = 0; j < hull->n_eq; ++j) {
3727                         isl_int *eq = hull->eq[j];
3728                         isl_pw_multi_aff *res;
3729
3730                         if (!isl_int_is_one(eq[o_out + i]) &&
3731                             !isl_int_is_negone(eq[o_out + i]))
3732                                 continue;
3733                         if (isl_seq_first_non_zero(eq + o_out, i) != -1)
3734                                 continue;
3735                         if (isl_seq_first_non_zero(eq + o_out + i + 1,
3736                                                     n_out - (i + 1)) != -1)
3737                                 continue;
3738                         isl_seq_gcd(eq + o_div, n_div, &gcd);
3739                         if (isl_int_is_zero(gcd))
3740                                 continue;
3741                         if (isl_int_is_one(gcd))
3742                                 continue;
3743
3744                         res = pw_multi_aff_from_map_stride(map, hull,
3745                                                                 i, j, gcd);
3746                         isl_int_clear(gcd);
3747                         return res;
3748                 }
3749         }
3750
3751         isl_int_clear(gcd);
3752         isl_basic_map_free(hull);
3753         return pw_multi_aff_from_map_check_div(map);
3754 error:
3755         isl_map_free(map);
3756         return NULL;
3757 }
3758
3759 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_set(__isl_take isl_set *set)
3760 {
3761         return isl_pw_multi_aff_from_map(set);
3762 }
3763
3764 /* Return the piecewise affine expression "set ? 1 : 0".
3765  */
3766 __isl_give isl_pw_aff *isl_set_indicator_function(__isl_take isl_set *set)
3767 {
3768         isl_pw_aff *pa;
3769         isl_space *space = isl_set_get_space(set);
3770         isl_local_space *ls = isl_local_space_from_space(space);
3771         isl_aff *zero = isl_aff_zero_on_domain(isl_local_space_copy(ls));
3772         isl_aff *one = isl_aff_zero_on_domain(ls);
3773
3774         one = isl_aff_add_constant_si(one, 1);
3775         pa = isl_pw_aff_alloc(isl_set_copy(set), one);
3776         set = isl_set_complement(set);
3777         pa = isl_pw_aff_add_disjoint(pa, isl_pw_aff_alloc(set, zero));
3778
3779         return pa;
3780 }
3781
3782 /* Plug in "subs" for dimension "type", "pos" of "aff".
3783  *
3784  * Let i be the dimension to replace and let "subs" be of the form
3785  *
3786  *      f/d
3787  *
3788  * and "aff" of the form
3789  *
3790  *      (a i + g)/m
3791  *
3792  * The result is
3793  *
3794  *      (a f + d g')/(m d)
3795  *
3796  * where g' is the result of plugging in "subs" in each of the integer
3797  * divisions in g.
3798  */
3799 __isl_give isl_aff *isl_aff_substitute(__isl_take isl_aff *aff,
3800         enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs)
3801 {
3802         isl_ctx *ctx;
3803         isl_int v;
3804
3805         aff = isl_aff_cow(aff);
3806         if (!aff || !subs)
3807                 return isl_aff_free(aff);
3808
3809         ctx = isl_aff_get_ctx(aff);
3810         if (!isl_space_is_equal(aff->ls->dim, subs->ls->dim))
3811                 isl_die(ctx, isl_error_invalid,
3812                         "spaces don't match", return isl_aff_free(aff));
3813         if (isl_local_space_dim(subs->ls, isl_dim_div) != 0)
3814                 isl_die(ctx, isl_error_unsupported,
3815                         "cannot handle divs yet", return isl_aff_free(aff));
3816
3817         aff->ls = isl_local_space_substitute(aff->ls, type, pos, subs);
3818         if (!aff->ls)
3819                 return isl_aff_free(aff);
3820
3821         aff->v = isl_vec_cow(aff->v);
3822         if (!aff->v)
3823                 return isl_aff_free(aff);
3824
3825         pos += isl_local_space_offset(aff->ls, type);
3826
3827         isl_int_init(v);
3828         isl_seq_substitute(aff->v->el, pos, subs->v->el,
3829                             aff->v->size, subs->v->size, v);
3830         isl_int_clear(v);
3831
3832         return aff;
3833 }
3834
3835 /* Plug in "subs" for dimension "type", "pos" in each of the affine
3836  * expressions in "maff".
3837  */
3838 __isl_give isl_multi_aff *isl_multi_aff_substitute(
3839         __isl_take isl_multi_aff *maff, enum isl_dim_type type, unsigned pos,
3840         __isl_keep isl_aff *subs)
3841 {
3842         int i;
3843
3844         maff = isl_multi_aff_cow(maff);
3845         if (!maff || !subs)
3846                 return isl_multi_aff_free(maff);
3847
3848         if (type == isl_dim_in)
3849                 type = isl_dim_set;
3850
3851         for (i = 0; i < maff->n; ++i) {
3852                 maff->p[i] = isl_aff_substitute(maff->p[i], type, pos, subs);
3853                 if (!maff->p[i])
3854                         return isl_multi_aff_free(maff);
3855         }
3856
3857         return maff;
3858 }
3859
3860 /* Plug in "subs" for dimension "type", "pos" of "pma".
3861  *
3862  * pma is of the form
3863  *
3864  *      A_i(v) -> M_i(v)
3865  *
3866  * while subs is of the form
3867  *
3868  *      v' = B_j(v) -> S_j
3869  *
3870  * Each pair i,j such that C_ij = A_i \cap B_i is non-empty
3871  * has a contribution in the result, in particular
3872  *
3873  *      C_ij(S_j) -> M_i(S_j)
3874  *
3875  * Note that plugging in S_j in C_ij may also result in an empty set
3876  * and this contribution should simply be discarded.
3877  */
3878 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_substitute(
3879         __isl_take isl_pw_multi_aff *pma, enum isl_dim_type type, unsigned pos,
3880         __isl_keep isl_pw_aff *subs)
3881 {
3882         int i, j, n;
3883         isl_pw_multi_aff *res;
3884
3885         if (!pma || !subs)
3886                 return isl_pw_multi_aff_free(pma);
3887
3888         n = pma->n * subs->n;
3889         res = isl_pw_multi_aff_alloc_size(isl_space_copy(pma->dim), n);
3890
3891         for (i = 0; i < pma->n; ++i) {
3892                 for (j = 0; j < subs->n; ++j) {
3893                         isl_set *common;
3894                         isl_multi_aff *res_ij;
3895                         int empty;
3896
3897                         common = isl_set_intersect(
3898                                         isl_set_copy(pma->p[i].set),
3899                                         isl_set_copy(subs->p[j].set));
3900                         common = isl_set_substitute(common,
3901                                         type, pos, subs->p[j].aff);
3902                         empty = isl_set_plain_is_empty(common);
3903                         if (empty < 0 || empty) {
3904                                 isl_set_free(common);
3905                                 if (empty < 0)
3906                                         goto error;
3907                                 continue;
3908                         }
3909
3910                         res_ij = isl_multi_aff_substitute(
3911                                         isl_multi_aff_copy(pma->p[i].maff),
3912                                         type, pos, subs->p[j].aff);
3913
3914                         res = isl_pw_multi_aff_add_piece(res, common, res_ij);
3915                 }
3916         }
3917
3918         isl_pw_multi_aff_free(pma);
3919         return res;
3920 error:
3921         isl_pw_multi_aff_free(pma);
3922         isl_pw_multi_aff_free(res);
3923         return NULL;
3924 }
3925
3926 /* Compute the preimage of the affine expression "src" under "ma"
3927  * and put the result in "dst".  If "has_denom" is set (to one),
3928  * then "src" and "dst" have an extra initial denominator.
3929  * "n_div_ma" is the number of existentials in "ma"
3930  * "n_div_bset" is the number of existentials in "src"
3931  * The resulting "dst" (which is assumed to have been allocated by
3932  * the caller) contains coefficients for both sets of existentials,
3933  * first those in "ma" and then those in "src".
3934  * f, c1, c2 and g are temporary objects that have been initialized
3935  * by the caller.
3936  *
3937  * Let src represent the expression
3938  *
3939  *      (a(p) + b x + c(divs))/d
3940  *
3941  * and let ma represent the expressions
3942  *
3943  *      x_i = (r_i(p) + s_i(y) + t_i(divs'))/m_i
3944  *
3945  * We start out with the following expression for dst:
3946  *
3947  *      (a(p) + 0 y + 0 divs' + f \sum_i b_i x_i + c(divs))/d
3948  *
3949  * with the multiplication factor f initially equal to 1.
3950  * For each x_i that we substitute, we multiply the numerator
3951  * (and denominator) of dst by c_1 = m_i and add the numerator
3952  * of the x_i expression multiplied by c_2 = f b_i,
3953  * after removing the common factors of c_1 and c_2.
3954  * The multiplication factor f also needs to be multiplied by c_1
3955  * for the next x_j, j > i.
3956  */
3957 void isl_seq_preimage(isl_int *dst, isl_int *src,
3958         __isl_keep isl_multi_aff *ma, int n_div_ma, int n_div_bset,
3959         isl_int f, isl_int c1, isl_int c2, isl_int g, int has_denom)
3960 {
3961         int i;
3962         int n_param, n_in, n_out;
3963         int o_div_bset;
3964
3965         n_param = isl_multi_aff_dim(ma, isl_dim_param);
3966         n_in = isl_multi_aff_dim(ma, isl_dim_in);
3967         n_out = isl_multi_aff_dim(ma, isl_dim_out);
3968
3969         o_div_bset = has_denom + 1 + n_param + n_in + n_div_ma;
3970
3971         isl_seq_cpy(dst, src, has_denom + 1 + n_param);
3972         isl_seq_clr(dst + has_denom + 1 + n_param, n_in + n_div_ma);
3973         isl_seq_cpy(dst + o_div_bset,
3974                     src + has_denom + 1 + n_param + n_out, n_div_bset);
3975
3976         isl_int_set_si(f, 1);
3977
3978         for (i = 0; i < n_out; ++i) {
3979                 if (isl_int_is_zero(src[has_denom + 1 + n_param + i]))
3980                         continue;
3981                 isl_int_set(c1, ma->p[i]->v->el[0]);
3982                 isl_int_mul(c2, f, src[has_denom + 1 + n_param + i]);
3983                 isl_int_gcd(g, c1, c2);
3984                 isl_int_divexact(c1, c1, g);
3985                 isl_int_divexact(c2, c2, g);
3986
3987                 isl_int_mul(f, f, c1);
3988                 isl_seq_combine(dst + has_denom, c1, dst + has_denom,
3989                                 c2, ma->p[i]->v->el + 1, ma->p[i]->v->size - 1);
3990                 isl_seq_scale(dst + o_div_bset,
3991                                 dst + o_div_bset, c1, n_div_bset);
3992                 if (has_denom)
3993                         isl_int_mul(dst[0], dst[0], c1);
3994         }
3995 }
3996
3997 /* Compute the pullback of "aff" by the function represented by "ma".
3998  * In other words, plug in "ma" in "aff".  The result is an affine expression
3999  * defined over the domain space of "ma".
4000  *
4001  * If "aff" is represented by
4002  *
4003  *      (a(p) + b x + c(divs))/d
4004  *
4005  * and ma is represented by
4006  *
4007  *      x = D(p) + F(y) + G(divs')
4008  *
4009  * then the result is
4010  *
4011  *      (a(p) + b D(p) + b F(y) + b G(divs') + c(divs))/d
4012  *
4013  * The divs in the local space of the input are similarly adjusted
4014  * through a call to isl_local_space_preimage_multi_aff.
4015  */
4016 __isl_give isl_aff *isl_aff_pullback_multi_aff(__isl_take isl_aff *aff,
4017         __isl_take isl_multi_aff *ma)
4018 {
4019         isl_aff *res = NULL;
4020         isl_local_space *ls;
4021         int n_div_aff, n_div_ma;
4022         isl_int f, c1, c2, g;
4023
4024         ma = isl_multi_aff_align_divs(ma);
4025         if (!aff || !ma)
4026                 goto error;
4027
4028         n_div_aff = isl_aff_dim(aff, isl_dim_div);
4029         n_div_ma = ma->n ? isl_aff_dim(ma->p[0], isl_dim_div) : 0;
4030
4031         ls = isl_aff_get_domain_local_space(aff);
4032         ls = isl_local_space_preimage_multi_aff(ls, isl_multi_aff_copy(ma));
4033         res = isl_aff_alloc(ls);
4034         if (!res)
4035                 goto error;
4036
4037         isl_int_init(f);
4038         isl_int_init(c1);
4039         isl_int_init(c2);
4040         isl_int_init(g);
4041
4042         isl_seq_preimage(res->v->el, aff->v->el, ma, n_div_ma, n_div_aff,
4043                         f, c1, c2, g, 1);
4044
4045         isl_int_clear(f);
4046         isl_int_clear(c1);
4047         isl_int_clear(c2);
4048         isl_int_clear(g);
4049
4050         isl_aff_free(aff);
4051         isl_multi_aff_free(ma);
4052         res = isl_aff_normalize(res);
4053         return res;
4054 error:
4055         isl_aff_free(aff);
4056         isl_multi_aff_free(ma);
4057         isl_aff_free(res);
4058         return NULL;
4059 }
4060
4061 /* Compute the pullback of "ma1" by the function represented by "ma2".
4062  * In other words, plug in "ma2" in "ma1".
4063  */
4064 __isl_give isl_multi_aff *isl_multi_aff_pullback_multi_aff(
4065         __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2)
4066 {
4067         int i;
4068         isl_space *space = NULL;
4069
4070         ma2 = isl_multi_aff_align_divs(ma2);
4071         ma1 = isl_multi_aff_cow(ma1);
4072         if (!ma1 || !ma2)
4073                 goto error;
4074
4075         space = isl_space_join(isl_multi_aff_get_space(ma2),
4076                                 isl_multi_aff_get_space(ma1));
4077
4078         for (i = 0; i < ma1->n; ++i) {
4079                 ma1->p[i] = isl_aff_pullback_multi_aff(ma1->p[i],
4080                                                     isl_multi_aff_copy(ma2));
4081                 if (!ma1->p[i])
4082                         goto error;
4083         }
4084
4085         ma1 = isl_multi_aff_reset_space(ma1, space);
4086         isl_multi_aff_free(ma2);
4087         return ma1;
4088 error:
4089         isl_space_free(space);
4090         isl_multi_aff_free(ma2);
4091         isl_multi_aff_free(ma1);
4092         return NULL;
4093 }
4094
4095 /* Extend the local space of "dst" to include the divs
4096  * in the local space of "src".
4097  */
4098 __isl_give isl_aff *isl_aff_align_divs(__isl_take isl_aff *dst,
4099         __isl_keep isl_aff *src)
4100 {
4101         isl_ctx *ctx;
4102         int *exp1 = NULL;
4103         int *exp2 = NULL;
4104         isl_mat *div;
4105
4106         if (!src || !dst)
4107                 return isl_aff_free(dst);
4108
4109         ctx = isl_aff_get_ctx(src);
4110         if (!isl_space_is_equal(src->ls->dim, dst->ls->dim))
4111                 isl_die(ctx, isl_error_invalid,
4112                         "spaces don't match", goto error);
4113
4114         if (src->ls->div->n_row == 0)
4115                 return dst;
4116
4117         exp1 = isl_alloc_array(ctx, int, src->ls->div->n_row);
4118         exp2 = isl_alloc_array(ctx, int, dst->ls->div->n_row);
4119         if (!exp1 || !exp2)
4120                 goto error;
4121
4122         div = isl_merge_divs(src->ls->div, dst->ls->div, exp1, exp2);
4123         dst = isl_aff_expand_divs(dst, div, exp2);
4124         free(exp1);
4125         free(exp2);
4126
4127         return dst;
4128 error:
4129         free(exp1);
4130         free(exp2);
4131         return isl_aff_free(dst);
4132 }
4133
4134 /* Adjust the local spaces of the affine expressions in "maff"
4135  * such that they all have the save divs.
4136  */
4137 __isl_give isl_multi_aff *isl_multi_aff_align_divs(
4138         __isl_take isl_multi_aff *maff)
4139 {
4140         int i;
4141
4142         if (!maff)
4143                 return NULL;
4144         if (maff->n == 0)
4145                 return maff;
4146         maff = isl_multi_aff_cow(maff);
4147         if (!maff)
4148                 return NULL;
4149
4150         for (i = 1; i < maff->n; ++i)
4151                 maff->p[0] = isl_aff_align_divs(maff->p[0], maff->p[i]);
4152         for (i = 1; i < maff->n; ++i) {
4153                 maff->p[i] = isl_aff_align_divs(maff->p[i], maff->p[0]);
4154                 if (!maff->p[i])
4155                         return isl_multi_aff_free(maff);
4156         }
4157
4158         return maff;
4159 }
4160
4161 __isl_give isl_aff *isl_aff_lift(__isl_take isl_aff *aff)
4162 {
4163         aff = isl_aff_cow(aff);
4164         if (!aff)
4165                 return NULL;
4166
4167         aff->ls = isl_local_space_lift(aff->ls);
4168         if (!aff->ls)
4169                 return isl_aff_free(aff);
4170
4171         return aff;
4172 }
4173
4174 /* Lift "maff" to a space with extra dimensions such that the result
4175  * has no more existentially quantified variables.
4176  * If "ls" is not NULL, then *ls is assigned the local space that lies
4177  * at the basis of the lifting applied to "maff".
4178  */
4179 __isl_give isl_multi_aff *isl_multi_aff_lift(__isl_take isl_multi_aff *maff,
4180         __isl_give isl_local_space **ls)
4181 {
4182         int i;
4183         isl_space *space;
4184         unsigned n_div;
4185
4186         if (ls)
4187                 *ls = NULL;
4188
4189         if (!maff)
4190                 return NULL;
4191
4192         if (maff->n == 0) {
4193                 if (ls) {
4194                         isl_space *space = isl_multi_aff_get_domain_space(maff);
4195                         *ls = isl_local_space_from_space(space);
4196                         if (!*ls)
4197                                 return isl_multi_aff_free(maff);
4198                 }
4199                 return maff;
4200         }
4201
4202         maff = isl_multi_aff_cow(maff);
4203         maff = isl_multi_aff_align_divs(maff);
4204         if (!maff)
4205                 return NULL;
4206
4207         n_div = isl_aff_dim(maff->p[0], isl_dim_div);
4208         space = isl_multi_aff_get_space(maff);
4209         space = isl_space_lift(isl_space_domain(space), n_div);
4210         space = isl_space_extend_domain_with_range(space,
4211                                                 isl_multi_aff_get_space(maff));
4212         if (!space)
4213                 return isl_multi_aff_free(maff);
4214         isl_space_free(maff->space);
4215         maff->space = space;
4216
4217         if (ls) {
4218                 *ls = isl_aff_get_domain_local_space(maff->p[0]);
4219                 if (!*ls)
4220                         return isl_multi_aff_free(maff);
4221         }
4222
4223         for (i = 0; i < maff->n; ++i) {
4224                 maff->p[i] = isl_aff_lift(maff->p[i]);
4225                 if (!maff->p[i])
4226                         goto error;
4227         }
4228
4229         return maff;
4230 error:
4231         if (ls)
4232                 isl_local_space_free(*ls);
4233         return isl_multi_aff_free(maff);
4234 }
4235
4236
4237 /* Extract an isl_pw_aff corresponding to output dimension "pos" of "pma".
4238  */
4239 __isl_give isl_pw_aff *isl_pw_multi_aff_get_pw_aff(
4240         __isl_keep isl_pw_multi_aff *pma, int pos)
4241 {
4242         int i;
4243         int n_out;
4244         isl_space *space;
4245         isl_pw_aff *pa;
4246
4247         if (!pma)
4248                 return NULL;
4249
4250         n_out = isl_pw_multi_aff_dim(pma, isl_dim_out);
4251         if (pos < 0 || pos >= n_out)
4252                 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
4253                         "index out of bounds", return NULL);
4254
4255         space = isl_pw_multi_aff_get_space(pma);
4256         space = isl_space_drop_dims(space, isl_dim_out,
4257                                     pos + 1, n_out - pos - 1);
4258         space = isl_space_drop_dims(space, isl_dim_out, 0, pos);
4259
4260         pa = isl_pw_aff_alloc_size(space, pma->n);
4261         for (i = 0; i < pma->n; ++i) {
4262                 isl_aff *aff;
4263                 aff = isl_multi_aff_get_aff(pma->p[i].maff, pos);
4264                 pa = isl_pw_aff_add_piece(pa, isl_set_copy(pma->p[i].set), aff);
4265         }
4266
4267         return pa;
4268 }
4269
4270 /* Return an isl_pw_multi_aff with the given "set" as domain and
4271  * an unnamed zero-dimensional range.
4272  */
4273 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_domain(
4274         __isl_take isl_set *set)
4275 {
4276         isl_multi_aff *ma;
4277         isl_space *space;
4278
4279         space = isl_set_get_space(set);
4280         space = isl_space_from_domain(space);
4281         ma = isl_multi_aff_zero(space);
4282         return isl_pw_multi_aff_alloc(set, ma);
4283 }
4284
4285 /* Add an isl_pw_multi_aff with the given "set" as domain and
4286  * an unnamed zero-dimensional range to *user.
4287  */
4288 static int add_pw_multi_aff_from_domain(__isl_take isl_set *set, void *user)
4289 {
4290         isl_union_pw_multi_aff **upma = user;
4291         isl_pw_multi_aff *pma;
4292
4293         pma = isl_pw_multi_aff_from_domain(set);
4294         *upma = isl_union_pw_multi_aff_add_pw_multi_aff(*upma, pma);
4295
4296         return 0;
4297 }
4298
4299 /* Return an isl_union_pw_multi_aff with the given "uset" as domain and
4300  * an unnamed zero-dimensional range.
4301  */
4302 __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_from_domain(
4303         __isl_take isl_union_set *uset)
4304 {
4305         isl_space *space;
4306         isl_union_pw_multi_aff *upma;
4307
4308         if (!uset)
4309                 return NULL;
4310
4311         space = isl_union_set_get_space(uset);
4312         upma = isl_union_pw_multi_aff_empty(space);
4313
4314         if (isl_union_set_foreach_set(uset,
4315                                     &add_pw_multi_aff_from_domain, &upma) < 0)
4316                 goto error;
4317
4318         isl_union_set_free(uset);
4319         return upma;
4320 error:
4321         isl_union_set_free(uset);
4322         isl_union_pw_multi_aff_free(upma);
4323         return NULL;
4324 }
4325
4326 /* Convert "pma" to an isl_map and add it to *umap.
4327  */
4328 static int map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma, void *user)
4329 {
4330         isl_union_map **umap = user;
4331         isl_map *map;
4332
4333         map = isl_map_from_pw_multi_aff(pma);
4334         *umap = isl_union_map_add_map(*umap, map);
4335
4336         return 0;
4337 }
4338
4339 /* Construct a union map mapping the domain of the union
4340  * piecewise multi-affine expression to its range, with each dimension
4341  * in the range equated to the corresponding affine expression on its cell.
4342  */
4343 __isl_give isl_union_map *isl_union_map_from_union_pw_multi_aff(
4344         __isl_take isl_union_pw_multi_aff *upma)
4345 {
4346         isl_space *space;
4347         isl_union_map *umap;
4348
4349         if (!upma)
4350                 return NULL;
4351
4352         space = isl_union_pw_multi_aff_get_space(upma);
4353         umap = isl_union_map_empty(space);
4354
4355         if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma,
4356                                         &map_from_pw_multi_aff, &umap) < 0)
4357                 goto error;
4358
4359         isl_union_pw_multi_aff_free(upma);
4360         return umap;
4361 error:
4362         isl_union_pw_multi_aff_free(upma);
4363         isl_union_map_free(umap);
4364         return NULL;
4365 }
4366
4367 /* Local data for bin_entry and the callback "fn".
4368  */
4369 struct isl_union_pw_multi_aff_bin_data {
4370         isl_union_pw_multi_aff *upma2;
4371         isl_union_pw_multi_aff *res;
4372         isl_pw_multi_aff *pma;
4373         int (*fn)(void **entry, void *user);
4374 };
4375
4376 /* Given an isl_pw_multi_aff from upma1, store it in data->pma
4377  * and call data->fn for each isl_pw_multi_aff in data->upma2.
4378  */
4379 static int bin_entry(void **entry, void *user)
4380 {
4381         struct isl_union_pw_multi_aff_bin_data *data = user;
4382         isl_pw_multi_aff *pma = *entry;
4383
4384         data->pma = pma;
4385         if (isl_hash_table_foreach(data->upma2->dim->ctx, &data->upma2->table,
4386                                    data->fn, data) < 0)
4387                 return -1;
4388
4389         return 0;
4390 }
4391
4392 /* Call "fn" on each pair of isl_pw_multi_affs in "upma1" and "upma2".
4393  * The isl_pw_multi_aff from upma1 is stored in data->pma (where data is
4394  * passed as user field) and the isl_pw_multi_aff from upma2 is available
4395  * as *entry.  The callback should adjust data->res if desired.
4396  */
4397 static __isl_give isl_union_pw_multi_aff *bin_op(
4398         __isl_take isl_union_pw_multi_aff *upma1,
4399         __isl_take isl_union_pw_multi_aff *upma2,
4400         int (*fn)(void **entry, void *user))
4401 {
4402         isl_space *space;
4403         struct isl_union_pw_multi_aff_bin_data data = { NULL, NULL, NULL, fn };
4404
4405         space = isl_union_pw_multi_aff_get_space(upma2);
4406         upma1 = isl_union_pw_multi_aff_align_params(upma1, space);
4407         space = isl_union_pw_multi_aff_get_space(upma1);
4408         upma2 = isl_union_pw_multi_aff_align_params(upma2, space);
4409
4410         if (!upma1 || !upma2)
4411                 goto error;
4412
4413         data.upma2 = upma2;
4414         data.res = isl_union_pw_multi_aff_alloc(isl_space_copy(upma1->dim),
4415                                        upma1->table.n);
4416         if (isl_hash_table_foreach(upma1->dim->ctx, &upma1->table,
4417                                    &bin_entry, &data) < 0)
4418                 goto error;
4419
4420         isl_union_pw_multi_aff_free(upma1);
4421         isl_union_pw_multi_aff_free(upma2);
4422         return data.res;
4423 error:
4424         isl_union_pw_multi_aff_free(upma1);
4425         isl_union_pw_multi_aff_free(upma2);
4426         isl_union_pw_multi_aff_free(data.res);
4427         return NULL;
4428 }
4429
4430 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
4431  * construct an isl_pw_multi_aff (A * C) -> [B -> D].
4432  */
4433 static __isl_give isl_pw_multi_aff *pw_multi_aff_range_product(
4434         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4435 {
4436         isl_space *space;
4437
4438         space = isl_space_range_product(isl_pw_multi_aff_get_space(pma1),
4439                                         isl_pw_multi_aff_get_space(pma2));
4440         return isl_pw_multi_aff_on_shared_domain_in(pma1, pma2, space,
4441                                             &isl_multi_aff_range_product);
4442 }
4443
4444 /* Given two isl_pw_multi_affs A -> B and C -> D,
4445  * construct an isl_pw_multi_aff (A * C) -> [B -> D].
4446  */
4447 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_range_product(
4448         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4449 {
4450         return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
4451                                             &pw_multi_aff_range_product);
4452 }
4453
4454 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
4455  * construct an isl_pw_multi_aff (A * C) -> (B, D).
4456  */
4457 static __isl_give isl_pw_multi_aff *pw_multi_aff_flat_range_product(
4458         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4459 {
4460         isl_space *space;
4461
4462         space = isl_space_range_product(isl_pw_multi_aff_get_space(pma1),
4463                                         isl_pw_multi_aff_get_space(pma2));
4464         space = isl_space_flatten_range(space);
4465         return isl_pw_multi_aff_on_shared_domain_in(pma1, pma2, space,
4466                                             &isl_multi_aff_flat_range_product);
4467 }
4468
4469 /* Given two isl_pw_multi_affs A -> B and C -> D,
4470  * construct an isl_pw_multi_aff (A * C) -> (B, D).
4471  */
4472 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_flat_range_product(
4473         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4474 {
4475         return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
4476                                             &pw_multi_aff_flat_range_product);
4477 }
4478
4479 /* If data->pma and *entry have the same domain space, then compute
4480  * their flat range product and the result to data->res.
4481  */
4482 static int flat_range_product_entry(void **entry, void *user)
4483 {
4484         struct isl_union_pw_multi_aff_bin_data *data = user;
4485         isl_pw_multi_aff *pma2 = *entry;
4486
4487         if (!isl_space_tuple_match(data->pma->dim, isl_dim_in,
4488                                  pma2->dim, isl_dim_in))
4489                 return 0;
4490
4491         pma2 = isl_pw_multi_aff_flat_range_product(
4492                                         isl_pw_multi_aff_copy(data->pma),
4493                                         isl_pw_multi_aff_copy(pma2));
4494
4495         data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res, pma2);
4496
4497         return 0;
4498 }
4499
4500 /* Given two isl_union_pw_multi_affs A -> B and C -> D,
4501  * construct an isl_union_pw_multi_aff (A * C) -> (B, D).
4502  */
4503 __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_flat_range_product(
4504         __isl_take isl_union_pw_multi_aff *upma1,
4505         __isl_take isl_union_pw_multi_aff *upma2)
4506 {
4507         return bin_op(upma1, upma2, &flat_range_product_entry);
4508 }
4509
4510 /* Replace the affine expressions at position "pos" in "pma" by "pa".
4511  * The parameters are assumed to have been aligned.
4512  *
4513  * The implementation essentially performs an isl_pw_*_on_shared_domain,
4514  * except that it works on two different isl_pw_* types.
4515  */
4516 static __isl_give isl_pw_multi_aff *pw_multi_aff_set_pw_aff(
4517         __isl_take isl_pw_multi_aff *pma, unsigned pos,
4518         __isl_take isl_pw_aff *pa)
4519 {
4520         int i, j, n;
4521         isl_pw_multi_aff *res = NULL;
4522
4523         if (!pma || !pa)
4524                 goto error;
4525
4526         if (!isl_space_tuple_match(pma->dim, isl_dim_in, pa->dim, isl_dim_in))
4527                 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
4528                         "domains don't match", goto error);
4529         if (pos >= isl_pw_multi_aff_dim(pma, isl_dim_out))
4530                 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
4531                         "index out of bounds", goto error);
4532
4533         n = pma->n * pa->n;
4534         res = isl_pw_multi_aff_alloc_size(isl_pw_multi_aff_get_space(pma), n);
4535
4536         for (i = 0; i < pma->n; ++i) {
4537                 for (j = 0; j < pa->n; ++j) {
4538                         isl_set *common;
4539                         isl_multi_aff *res_ij;
4540                         int empty;
4541
4542                         common = isl_set_intersect(isl_set_copy(pma->p[i].set),
4543                                                    isl_set_copy(pa->p[j].set));
4544                         empty = isl_set_plain_is_empty(common);
4545                         if (empty < 0 || empty) {
4546                                 isl_set_free(common);
4547                                 if (empty < 0)
4548                                         goto error;
4549                                 continue;
4550                         }
4551
4552                         res_ij = isl_multi_aff_set_aff(
4553                                         isl_multi_aff_copy(pma->p[i].maff), pos,
4554                                         isl_aff_copy(pa->p[j].aff));
4555                         res_ij = isl_multi_aff_gist(res_ij,
4556                                         isl_set_copy(common));
4557
4558                         res = isl_pw_multi_aff_add_piece(res, common, res_ij);
4559                 }
4560         }
4561
4562         isl_pw_multi_aff_free(pma);
4563         isl_pw_aff_free(pa);
4564         return res;
4565 error:
4566         isl_pw_multi_aff_free(pma);
4567         isl_pw_aff_free(pa);
4568         return isl_pw_multi_aff_free(res);
4569 }
4570
4571 /* Replace the affine expressions at position "pos" in "pma" by "pa".
4572  */
4573 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_set_pw_aff(
4574         __isl_take isl_pw_multi_aff *pma, unsigned pos,
4575         __isl_take isl_pw_aff *pa)
4576 {
4577         if (!pma || !pa)
4578                 goto error;
4579         if (isl_space_match(pma->dim, isl_dim_param, pa->dim, isl_dim_param))
4580                 return pw_multi_aff_set_pw_aff(pma, pos, pa);
4581         if (!isl_space_has_named_params(pma->dim) ||
4582             !isl_space_has_named_params(pa->dim))
4583                 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
4584                         "unaligned unnamed parameters", goto error);
4585         pma = isl_pw_multi_aff_align_params(pma, isl_pw_aff_get_space(pa));
4586         pa = isl_pw_aff_align_params(pa, isl_pw_multi_aff_get_space(pma));
4587         return pw_multi_aff_set_pw_aff(pma, pos, pa);
4588 error:
4589         isl_pw_multi_aff_free(pma);
4590         isl_pw_aff_free(pa);
4591         return NULL;
4592 }
4593
4594 #undef BASE
4595 #define BASE pw_aff
4596
4597 #include <isl_multi_templ.c>