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;
2630
2631         if (!list)
2632                 return NULL;
2633         if (list->n == 0)
2634                 return list;
2635
2636         for (i = 0; i < list->n; ++i) {
2637                 isl_pw_aff *pa;
2638
2639                 pa = isl_pw_aff_list_get_pw_aff(list, i);
2640                 pa = isl_pw_aff_set_rational(pa);
2641                 list = isl_pw_aff_list_set_pw_aff(list, i, pa);
2642         }
2643
2644         return list;
2645 }
2646
2647 #undef BASE
2648 #define BASE aff
2649
2650 #include <isl_multi_templ.c>
2651
2652 /* Create an isl_pw_multi_aff with the given isl_multi_aff on a universe
2653  * domain.
2654  */
2655 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_multi_aff(
2656         __isl_take isl_multi_aff *ma)
2657 {
2658         isl_set *dom = isl_set_universe(isl_multi_aff_get_domain_space(ma));
2659         return isl_pw_multi_aff_alloc(dom, ma);
2660 }
2661
2662 /* Create a piecewise multi-affine expression in the given space that maps each
2663  * input dimension to the corresponding output dimension.
2664  */
2665 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_identity(
2666         __isl_take isl_space *space)
2667 {
2668         return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_identity(space));
2669 }
2670
2671 __isl_give isl_multi_aff *isl_multi_aff_add(__isl_take isl_multi_aff *maff1,
2672         __isl_take isl_multi_aff *maff2)
2673 {
2674         int i;
2675         isl_ctx *ctx;
2676
2677         maff1 = isl_multi_aff_cow(maff1);
2678         if (!maff1 || !maff2)
2679                 goto error;
2680
2681         ctx = isl_multi_aff_get_ctx(maff1);
2682         if (!isl_space_is_equal(maff1->space, maff2->space))
2683                 isl_die(ctx, isl_error_invalid,
2684                         "spaces don't match", goto error);
2685
2686         for (i = 0; i < maff1->n; ++i) {
2687                 maff1->p[i] = isl_aff_add(maff1->p[i],
2688                                             isl_aff_copy(maff2->p[i]));
2689                 if (!maff1->p[i])
2690                         goto error;
2691         }
2692
2693         isl_multi_aff_free(maff2);
2694         return maff1;
2695 error:
2696         isl_multi_aff_free(maff1);
2697         isl_multi_aff_free(maff2);
2698         return NULL;
2699 }
2700
2701 /* Given two multi-affine expressions A -> B and C -> D,
2702  * construct a multi-affine expression [A -> C] -> [B -> D].
2703  */
2704 __isl_give isl_multi_aff *isl_multi_aff_product(
2705         __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2)
2706 {
2707         int i;
2708         isl_aff *aff;
2709         isl_space *space;
2710         isl_multi_aff *res;
2711         int in1, in2, out1, out2;
2712
2713         in1 = isl_multi_aff_dim(ma1, isl_dim_in);
2714         in2 = isl_multi_aff_dim(ma2, isl_dim_in);
2715         out1 = isl_multi_aff_dim(ma1, isl_dim_out);
2716         out2 = isl_multi_aff_dim(ma2, isl_dim_out);
2717         space = isl_space_product(isl_multi_aff_get_space(ma1),
2718                                   isl_multi_aff_get_space(ma2));
2719         res = isl_multi_aff_alloc(isl_space_copy(space));
2720         space = isl_space_domain(space);
2721
2722         for (i = 0; i < out1; ++i) {
2723                 aff = isl_multi_aff_get_aff(ma1, i);
2724                 aff = isl_aff_insert_dims(aff, isl_dim_in, in1, in2);
2725                 aff = isl_aff_reset_domain_space(aff, isl_space_copy(space));
2726                 res = isl_multi_aff_set_aff(res, i, aff);
2727         }
2728
2729         for (i = 0; i < out2; ++i) {
2730                 aff = isl_multi_aff_get_aff(ma2, i);
2731                 aff = isl_aff_insert_dims(aff, isl_dim_in, 0, in1);
2732                 aff = isl_aff_reset_domain_space(aff, isl_space_copy(space));
2733                 res = isl_multi_aff_set_aff(res, out1 + i, aff);
2734         }
2735
2736         isl_space_free(space);
2737         isl_multi_aff_free(ma1);
2738         isl_multi_aff_free(ma2);
2739         return res;
2740 }
2741
2742 /* Exploit the equalities in "eq" to simplify the affine expressions.
2743  */
2744 static __isl_give isl_multi_aff *isl_multi_aff_substitute_equalities(
2745         __isl_take isl_multi_aff *maff, __isl_take isl_basic_set *eq)
2746 {
2747         int i;
2748
2749         maff = isl_multi_aff_cow(maff);
2750         if (!maff || !eq)
2751                 goto error;
2752
2753         for (i = 0; i < maff->n; ++i) {
2754                 maff->p[i] = isl_aff_substitute_equalities(maff->p[i],
2755                                                     isl_basic_set_copy(eq));
2756                 if (!maff->p[i])
2757                         goto error;
2758         }
2759
2760         isl_basic_set_free(eq);
2761         return maff;
2762 error:
2763         isl_basic_set_free(eq);
2764         isl_multi_aff_free(maff);
2765         return NULL;
2766 }
2767
2768 __isl_give isl_multi_aff *isl_multi_aff_scale(__isl_take isl_multi_aff *maff,
2769         isl_int f)
2770 {
2771         int i;
2772
2773         maff = isl_multi_aff_cow(maff);
2774         if (!maff)
2775                 return NULL;
2776
2777         for (i = 0; i < maff->n; ++i) {
2778                 maff->p[i] = isl_aff_scale(maff->p[i], f);
2779                 if (!maff->p[i])
2780                         return isl_multi_aff_free(maff);
2781         }
2782
2783         return maff;
2784 }
2785
2786 __isl_give isl_multi_aff *isl_multi_aff_add_on_domain(__isl_keep isl_set *dom,
2787         __isl_take isl_multi_aff *maff1, __isl_take isl_multi_aff *maff2)
2788 {
2789         maff1 = isl_multi_aff_add(maff1, maff2);
2790         maff1 = isl_multi_aff_gist(maff1, isl_set_copy(dom));
2791         return maff1;
2792 }
2793
2794 int isl_multi_aff_is_empty(__isl_keep isl_multi_aff *maff)
2795 {
2796         if (!maff)
2797                 return -1;
2798
2799         return 0;
2800 }
2801
2802 int isl_multi_aff_plain_is_equal(__isl_keep isl_multi_aff *maff1,
2803         __isl_keep isl_multi_aff *maff2)
2804 {
2805         int i;
2806         int equal;
2807
2808         if (!maff1 || !maff2)
2809                 return -1;
2810         if (maff1->n != maff2->n)
2811                 return 0;
2812         equal = isl_space_is_equal(maff1->space, maff2->space);
2813         if (equal < 0 || !equal)
2814                 return equal;
2815
2816         for (i = 0; i < maff1->n; ++i) {
2817                 equal = isl_aff_plain_is_equal(maff1->p[i], maff2->p[i]);
2818                 if (equal < 0 || !equal)
2819                         return equal;
2820         }
2821
2822         return 1;
2823 }
2824
2825 /* Return the set of domain elements where "ma1" is lexicographically
2826  * smaller than or equal to "ma2".
2827  */
2828 __isl_give isl_set *isl_multi_aff_lex_le_set(__isl_take isl_multi_aff *ma1,
2829         __isl_take isl_multi_aff *ma2)
2830 {
2831         return isl_multi_aff_lex_ge_set(ma2, ma1);
2832 }
2833
2834 /* Return the set of domain elements where "ma1" is lexicographically
2835  * greater than or equal to "ma2".
2836  */
2837 __isl_give isl_set *isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff *ma1,
2838         __isl_take isl_multi_aff *ma2)
2839 {
2840         isl_space *space;
2841         isl_map *map1, *map2;
2842         isl_map *map, *ge;
2843
2844         map1 = isl_map_from_multi_aff(ma1);
2845         map2 = isl_map_from_multi_aff(ma2);
2846         map = isl_map_range_product(map1, map2);
2847         space = isl_space_range(isl_map_get_space(map));
2848         space = isl_space_domain(isl_space_unwrap(space));
2849         ge = isl_map_lex_ge(space);
2850         map = isl_map_intersect_range(map, isl_map_wrap(ge));
2851
2852         return isl_map_domain(map);
2853 }
2854
2855 #undef PW
2856 #define PW isl_pw_multi_aff
2857 #undef EL
2858 #define EL isl_multi_aff
2859 #undef EL_IS_ZERO
2860 #define EL_IS_ZERO is_empty
2861 #undef ZERO
2862 #define ZERO empty
2863 #undef IS_ZERO
2864 #define IS_ZERO is_empty
2865 #undef FIELD
2866 #define FIELD maff
2867 #undef DEFAULT_IS_ZERO
2868 #define DEFAULT_IS_ZERO 0
2869
2870 #define NO_NEG
2871 #define NO_EVAL
2872 #define NO_OPT
2873 #define NO_INVOLVES_DIMS
2874 #define NO_MOVE_DIMS
2875 #define NO_INSERT_DIMS
2876 #define NO_LIFT
2877 #define NO_MORPH
2878
2879 #include <isl_pw_templ.c>
2880
2881 #undef UNION
2882 #define UNION isl_union_pw_multi_aff
2883 #undef PART
2884 #define PART isl_pw_multi_aff
2885 #undef PARTS
2886 #define PARTS pw_multi_aff
2887 #define ALIGN_DOMAIN
2888
2889 #define NO_EVAL
2890
2891 #include <isl_union_templ.c>
2892
2893 /* Given a function "cmp" that returns the set of elements where
2894  * "ma1" is "better" than "ma2", return the intersection of this
2895  * set with "dom1" and "dom2".
2896  */
2897 static __isl_give isl_set *shared_and_better(__isl_keep isl_set *dom1,
2898         __isl_keep isl_set *dom2, __isl_keep isl_multi_aff *ma1,
2899         __isl_keep isl_multi_aff *ma2,
2900         __isl_give isl_set *(*cmp)(__isl_take isl_multi_aff *ma1,
2901                                     __isl_take isl_multi_aff *ma2))
2902 {
2903         isl_set *common;
2904         isl_set *better;
2905         int is_empty;
2906
2907         common = isl_set_intersect(isl_set_copy(dom1), isl_set_copy(dom2));
2908         is_empty = isl_set_plain_is_empty(common);
2909         if (is_empty >= 0 && is_empty)
2910                 return common;
2911         if (is_empty < 0)
2912                 return isl_set_free(common);
2913         better = cmp(isl_multi_aff_copy(ma1), isl_multi_aff_copy(ma2));
2914         better = isl_set_intersect(common, better);
2915
2916         return better;
2917 }
2918
2919 /* Given a function "cmp" that returns the set of elements where
2920  * "ma1" is "better" than "ma2", return a piecewise multi affine
2921  * expression defined on the union of the definition domains
2922  * of "pma1" and "pma2" that maps to the "best" of "pma1" and
2923  * "pma2" on each cell.  If only one of the two input functions
2924  * is defined on a given cell, then it is considered the best.
2925  */
2926 static __isl_give isl_pw_multi_aff *pw_multi_aff_union_opt(
2927         __isl_take isl_pw_multi_aff *pma1,
2928         __isl_take isl_pw_multi_aff *pma2,
2929         __isl_give isl_set *(*cmp)(__isl_take isl_multi_aff *ma1,
2930                                     __isl_take isl_multi_aff *ma2))
2931 {
2932         int i, j, n;
2933         isl_pw_multi_aff *res = NULL;
2934         isl_ctx *ctx;
2935         isl_set *set = NULL;
2936
2937         if (!pma1 || !pma2)
2938                 goto error;
2939
2940         ctx = isl_space_get_ctx(pma1->dim);
2941         if (!isl_space_is_equal(pma1->dim, pma2->dim))
2942                 isl_die(ctx, isl_error_invalid,
2943                         "arguments should live in the same space", goto error);
2944
2945         if (isl_pw_multi_aff_is_empty(pma1)) {
2946                 isl_pw_multi_aff_free(pma1);
2947                 return pma2;
2948         }
2949
2950         if (isl_pw_multi_aff_is_empty(pma2)) {
2951                 isl_pw_multi_aff_free(pma2);
2952                 return pma1;
2953         }
2954
2955         n = 2 * (pma1->n + 1) * (pma2->n + 1);
2956         res = isl_pw_multi_aff_alloc_size(isl_space_copy(pma1->dim), n);
2957
2958         for (i = 0; i < pma1->n; ++i) {
2959                 set = isl_set_copy(pma1->p[i].set);
2960                 for (j = 0; j < pma2->n; ++j) {
2961                         isl_set *better;
2962                         int is_empty;
2963
2964                         better = shared_and_better(pma2->p[j].set,
2965                                         pma1->p[i].set, pma2->p[j].maff,
2966                                         pma1->p[i].maff, cmp);
2967                         is_empty = isl_set_plain_is_empty(better);
2968                         if (is_empty < 0 || is_empty) {
2969                                 isl_set_free(better);
2970                                 if (is_empty < 0)
2971                                         goto error;
2972                                 continue;
2973                         }
2974                         set = isl_set_subtract(set, isl_set_copy(better));
2975
2976                         res = isl_pw_multi_aff_add_piece(res, better,
2977                                         isl_multi_aff_copy(pma2->p[j].maff));
2978                 }
2979                 res = isl_pw_multi_aff_add_piece(res, set,
2980                                         isl_multi_aff_copy(pma1->p[i].maff));
2981         }
2982
2983         for (j = 0; j < pma2->n; ++j) {
2984                 set = isl_set_copy(pma2->p[j].set);
2985                 for (i = 0; i < pma1->n; ++i)
2986                         set = isl_set_subtract(set,
2987                                         isl_set_copy(pma1->p[i].set));
2988                 res = isl_pw_multi_aff_add_piece(res, set,
2989                                         isl_multi_aff_copy(pma2->p[j].maff));
2990         }
2991
2992         isl_pw_multi_aff_free(pma1);
2993         isl_pw_multi_aff_free(pma2);
2994
2995         return res;
2996 error:
2997         isl_pw_multi_aff_free(pma1);
2998         isl_pw_multi_aff_free(pma2);
2999         isl_set_free(set);
3000         return isl_pw_multi_aff_free(res);
3001 }
3002
3003 static __isl_give isl_pw_multi_aff *pw_multi_aff_union_lexmax(
3004         __isl_take isl_pw_multi_aff *pma1,
3005         __isl_take isl_pw_multi_aff *pma2)
3006 {
3007         return pw_multi_aff_union_opt(pma1, pma2, &isl_multi_aff_lex_ge_set);
3008 }
3009
3010 /* Given two piecewise multi affine expressions, return a piecewise
3011  * multi-affine expression defined on the union of the definition domains
3012  * of the inputs that is equal to the lexicographic maximum of the two
3013  * inputs on each cell.  If only one of the two inputs is defined on
3014  * a given cell, then it is considered to be the maximum.
3015  */
3016 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_lexmax(
3017         __isl_take isl_pw_multi_aff *pma1,
3018         __isl_take isl_pw_multi_aff *pma2)
3019 {
3020         return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
3021                                                     &pw_multi_aff_union_lexmax);
3022 }
3023
3024 static __isl_give isl_pw_multi_aff *pw_multi_aff_union_lexmin(
3025         __isl_take isl_pw_multi_aff *pma1,
3026         __isl_take isl_pw_multi_aff *pma2)
3027 {
3028         return pw_multi_aff_union_opt(pma1, pma2, &isl_multi_aff_lex_le_set);
3029 }
3030
3031 /* Given two piecewise multi affine expressions, return a piecewise
3032  * multi-affine expression defined on the union of the definition domains
3033  * of the inputs that is equal to the lexicographic minimum of the two
3034  * inputs on each cell.  If only one of the two inputs is defined on
3035  * a given cell, then it is considered to be the minimum.
3036  */
3037 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_lexmin(
3038         __isl_take isl_pw_multi_aff *pma1,
3039         __isl_take isl_pw_multi_aff *pma2)
3040 {
3041         return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
3042                                                     &pw_multi_aff_union_lexmin);
3043 }
3044
3045 static __isl_give isl_pw_multi_aff *pw_multi_aff_add(
3046         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
3047 {
3048         return isl_pw_multi_aff_on_shared_domain(pma1, pma2,
3049                                                 &isl_multi_aff_add);
3050 }
3051
3052 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_add(
3053         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
3054 {
3055         return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
3056                                                 &pw_multi_aff_add);
3057 }
3058
3059 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_add(
3060         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
3061 {
3062         return isl_pw_multi_aff_union_add_(pma1, pma2);
3063 }
3064
3065 /* Given two piecewise multi-affine expressions A -> B and C -> D,
3066  * construct a piecewise multi-affine expression [A -> C] -> [B -> D].
3067  */
3068 static __isl_give isl_pw_multi_aff *pw_multi_aff_product(
3069         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
3070 {
3071         int i, j, n;
3072         isl_space *space;
3073         isl_pw_multi_aff *res;
3074
3075         if (!pma1 || !pma2)
3076                 goto error;
3077
3078         n = pma1->n * pma2->n;
3079         space = isl_space_product(isl_space_copy(pma1->dim),
3080                                   isl_space_copy(pma2->dim));
3081         res = isl_pw_multi_aff_alloc_size(space, n);
3082
3083         for (i = 0; i < pma1->n; ++i) {
3084                 for (j = 0; j < pma2->n; ++j) {
3085                         isl_set *domain;
3086                         isl_multi_aff *ma;
3087
3088                         domain = isl_set_product(isl_set_copy(pma1->p[i].set),
3089                                                  isl_set_copy(pma2->p[j].set));
3090                         ma = isl_multi_aff_product(
3091                                         isl_multi_aff_copy(pma1->p[i].maff),
3092                                         isl_multi_aff_copy(pma2->p[i].maff));
3093                         res = isl_pw_multi_aff_add_piece(res, domain, ma);
3094                 }
3095         }
3096
3097         isl_pw_multi_aff_free(pma1);
3098         isl_pw_multi_aff_free(pma2);
3099         return res;
3100 error:
3101         isl_pw_multi_aff_free(pma1);
3102         isl_pw_multi_aff_free(pma2);
3103         return NULL;
3104 }
3105
3106 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_product(
3107         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
3108 {
3109         return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
3110                                                 &pw_multi_aff_product);
3111 }
3112
3113 /* Construct a map mapping the domain of the piecewise multi-affine expression
3114  * to its range, with each dimension in the range equated to the
3115  * corresponding affine expression on its cell.
3116  */
3117 __isl_give isl_map *isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
3118 {
3119         int i;
3120         isl_map *map;
3121
3122         if (!pma)
3123                 return NULL;
3124
3125         map = isl_map_empty(isl_pw_multi_aff_get_space(pma));
3126
3127         for (i = 0; i < pma->n; ++i) {
3128                 isl_multi_aff *maff;
3129                 isl_basic_map *bmap;
3130                 isl_map *map_i;
3131
3132                 maff = isl_multi_aff_copy(pma->p[i].maff);
3133                 bmap = isl_basic_map_from_multi_aff(maff);
3134                 map_i = isl_map_from_basic_map(bmap);
3135                 map_i = isl_map_intersect_domain(map_i,
3136                                                 isl_set_copy(pma->p[i].set));
3137                 map = isl_map_union_disjoint(map, map_i);
3138         }
3139
3140         isl_pw_multi_aff_free(pma);
3141         return map;
3142 }
3143
3144 __isl_give isl_set *isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
3145 {
3146         if (!pma)
3147                 return NULL;
3148
3149         if (!isl_space_is_set(pma->dim))
3150                 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
3151                         "isl_pw_multi_aff cannot be converted into an isl_set",
3152                         return isl_pw_multi_aff_free(pma));
3153
3154         return isl_map_from_pw_multi_aff(pma);
3155 }
3156
3157 /* Given a basic map with a single output dimension that is defined
3158  * in terms of the parameters and input dimensions using an equality,
3159  * extract an isl_aff that expresses the output dimension in terms
3160  * of the parameters and input dimensions.
3161  *
3162  * Since some applications expect the result of isl_pw_multi_aff_from_map
3163  * to only contain integer affine expressions, we compute the floor
3164  * of the expression before returning.
3165  *
3166  * This function shares some similarities with
3167  * isl_basic_map_has_defining_equality and isl_constraint_get_bound.
3168  */
3169 static __isl_give isl_aff *extract_isl_aff_from_basic_map(
3170         __isl_take isl_basic_map *bmap)
3171 {
3172         int i;
3173         unsigned offset;
3174         unsigned total;
3175         isl_local_space *ls;
3176         isl_aff *aff;
3177
3178         if (!bmap)
3179                 return NULL;
3180         if (isl_basic_map_dim(bmap, isl_dim_out) != 1)
3181                 isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
3182                         "basic map should have a single output dimension",
3183                         goto error);
3184         offset = isl_basic_map_offset(bmap, isl_dim_out);
3185         total = isl_basic_map_total_dim(bmap);
3186         for (i = 0; i < bmap->n_eq; ++i) {
3187                 if (isl_int_is_zero(bmap->eq[i][offset]))
3188                         continue;
3189                 if (isl_seq_first_non_zero(bmap->eq[i] + offset + 1,
3190                                            1 + total - (offset + 1)) != -1)
3191                         continue;
3192                 break;
3193         }
3194         if (i >= bmap->n_eq)
3195                 isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
3196                         "unable to find suitable equality", goto error);
3197         ls = isl_basic_map_get_local_space(bmap);
3198         aff = isl_aff_alloc(isl_local_space_domain(ls));
3199         if (!aff)
3200                 goto error;
3201         if (isl_int_is_neg(bmap->eq[i][offset]))
3202                 isl_seq_cpy(aff->v->el + 1, bmap->eq[i], offset);
3203         else
3204                 isl_seq_neg(aff->v->el + 1, bmap->eq[i], offset);
3205         isl_seq_clr(aff->v->el + 1 + offset, aff->v->size - (1 + offset));
3206         isl_int_abs(aff->v->el[0], bmap->eq[i][offset]);
3207         isl_basic_map_free(bmap);
3208
3209         aff = isl_aff_remove_unused_divs(aff);
3210         aff = isl_aff_floor(aff);
3211         return aff;
3212 error:
3213         isl_basic_map_free(bmap);
3214         return NULL;
3215 }
3216
3217 /* Given a basic map where each output dimension is defined
3218  * in terms of the parameters and input dimensions using an equality,
3219  * extract an isl_multi_aff that expresses the output dimensions in terms
3220  * of the parameters and input dimensions.
3221  */
3222 static __isl_give isl_multi_aff *extract_isl_multi_aff_from_basic_map(
3223         __isl_take isl_basic_map *bmap)
3224 {
3225         int i;
3226         unsigned n_out;
3227         isl_multi_aff *ma;
3228
3229         if (!bmap)
3230                 return NULL;
3231
3232         ma = isl_multi_aff_alloc(isl_basic_map_get_space(bmap));
3233         n_out = isl_basic_map_dim(bmap, isl_dim_out);
3234
3235         for (i = 0; i < n_out; ++i) {
3236                 isl_basic_map *bmap_i;
3237                 isl_aff *aff;
3238
3239                 bmap_i = isl_basic_map_copy(bmap);
3240                 bmap_i = isl_basic_map_project_out(bmap_i, isl_dim_out,
3241                                                         i + 1, n_out - (1 + i));
3242                 bmap_i = isl_basic_map_project_out(bmap_i, isl_dim_out, 0, i);
3243                 aff = extract_isl_aff_from_basic_map(bmap_i);
3244                 ma = isl_multi_aff_set_aff(ma, i, aff);
3245         }
3246
3247         isl_basic_map_free(bmap);
3248
3249         return ma;
3250 }
3251
3252 /* Create an isl_pw_multi_aff that is equivalent to
3253  * isl_map_intersect_domain(isl_map_from_basic_map(bmap), domain).
3254  * The given basic map is such that each output dimension is defined
3255  * in terms of the parameters and input dimensions using an equality.
3256  */
3257 static __isl_give isl_pw_multi_aff *plain_pw_multi_aff_from_map(
3258         __isl_take isl_set *domain, __isl_take isl_basic_map *bmap)
3259 {
3260         isl_multi_aff *ma;
3261
3262         ma = extract_isl_multi_aff_from_basic_map(bmap);
3263         return isl_pw_multi_aff_alloc(domain, ma);
3264 }
3265
3266 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
3267  * This obviously only works if the input "map" is single-valued.
3268  * If so, we compute the lexicographic minimum of the image in the form
3269  * of an isl_pw_multi_aff.  Since the image is unique, it is equal
3270  * to its lexicographic minimum.
3271  * If the input is not single-valued, we produce an error.
3272  */
3273 static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_base(
3274         __isl_take isl_map *map)
3275 {
3276         int i;
3277         int sv;
3278         isl_pw_multi_aff *pma;
3279
3280         sv = isl_map_is_single_valued(map);
3281         if (sv < 0)
3282                 goto error;
3283         if (!sv)
3284                 isl_die(isl_map_get_ctx(map), isl_error_invalid,
3285                         "map is not single-valued", goto error);
3286         map = isl_map_make_disjoint(map);
3287         if (!map)
3288                 return NULL;
3289
3290         pma = isl_pw_multi_aff_empty(isl_map_get_space(map));
3291
3292         for (i = 0; i < map->n; ++i) {
3293                 isl_pw_multi_aff *pma_i;
3294                 isl_basic_map *bmap;
3295                 bmap = isl_basic_map_copy(map->p[i]);
3296                 pma_i = isl_basic_map_lexmin_pw_multi_aff(bmap);
3297                 pma = isl_pw_multi_aff_add_disjoint(pma, pma_i);
3298         }
3299
3300         isl_map_free(map);
3301         return pma;
3302 error:
3303         isl_map_free(map);
3304         return NULL;
3305 }
3306
3307 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
3308  * taking into account that the output dimension at position "d"
3309  * can be represented as
3310  *
3311  *      x = floor((e(...) + c1) / m)
3312  *
3313  * given that constraint "i" is of the form
3314  *
3315  *      e(...) + c1 - m x >= 0
3316  *
3317  *
3318  * Let "map" be of the form
3319  *
3320  *      A -> B
3321  *
3322  * We construct a mapping
3323  *
3324  *      A -> [A -> x = floor(...)]
3325  *
3326  * apply that to the map, obtaining
3327  *
3328  *      [A -> x = floor(...)] -> B
3329  *
3330  * and equate dimension "d" to x.
3331  * We then compute a isl_pw_multi_aff representation of the resulting map
3332  * and plug in the mapping above.
3333  */
3334 static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_div(
3335         __isl_take isl_map *map, __isl_take isl_basic_map *hull, int d, int i)
3336 {
3337         isl_ctx *ctx;
3338         isl_space *space;
3339         isl_local_space *ls;
3340         isl_multi_aff *ma;
3341         isl_aff *aff;
3342         isl_vec *v;
3343         isl_map *insert;
3344         int offset;
3345         int n;
3346         int n_in;
3347         isl_pw_multi_aff *pma;
3348         int is_set;
3349
3350         is_set = isl_map_is_set(map);
3351
3352         offset = isl_basic_map_offset(hull, isl_dim_out);
3353         ctx = isl_map_get_ctx(map);
3354         space = isl_space_domain(isl_map_get_space(map));
3355         n_in = isl_space_dim(space, isl_dim_set);
3356         n = isl_space_dim(space, isl_dim_all);
3357
3358         v = isl_vec_alloc(ctx, 1 + 1 + n);
3359         if (v) {
3360                 isl_int_neg(v->el[0], hull->ineq[i][offset + d]);
3361                 isl_seq_cpy(v->el + 1, hull->ineq[i], 1 + n);
3362         }
3363         isl_basic_map_free(hull);
3364
3365         ls = isl_local_space_from_space(isl_space_copy(space));
3366         aff = isl_aff_alloc_vec(ls, v);
3367         aff = isl_aff_floor(aff);
3368         if (is_set) {
3369                 isl_space_free(space);
3370                 ma = isl_multi_aff_from_aff(aff);
3371         } else {
3372                 ma = isl_multi_aff_identity(isl_space_map_from_set(space));
3373                 ma = isl_multi_aff_range_product(ma,
3374                                                 isl_multi_aff_from_aff(aff));
3375         }
3376
3377         insert = isl_map_from_multi_aff(isl_multi_aff_copy(ma));
3378         map = isl_map_apply_domain(map, insert);
3379         map = isl_map_equate(map, isl_dim_in, n_in, isl_dim_out, d);
3380         pma = isl_pw_multi_aff_from_map(map);
3381         pma = isl_pw_multi_aff_pullback_multi_aff(pma, ma);
3382
3383         return pma;
3384 }
3385
3386 /* Is constraint "c" of the form
3387  *
3388  *      e(...) + c1 - m x >= 0
3389  *
3390  * or
3391  *
3392  *      -e(...) + c2 + m x >= 0
3393  *
3394  * where m > 1 and e only depends on parameters and input dimemnsions?
3395  *
3396  * "offset" is the offset of the output dimensions
3397  * "pos" is the position of output dimension x.
3398  */
3399 static int is_potential_div_constraint(isl_int *c, int offset, int d, int total)
3400 {
3401         if (isl_int_is_zero(c[offset + d]))
3402                 return 0;
3403         if (isl_int_is_one(c[offset + d]))
3404                 return 0;
3405         if (isl_int_is_negone(c[offset + d]))
3406                 return 0;
3407         if (isl_seq_first_non_zero(c + offset, d) != -1)
3408                 return 0;
3409         if (isl_seq_first_non_zero(c + offset + d + 1,
3410                                     total - (offset + d + 1)) != -1)
3411                 return 0;
3412         return 1;
3413 }
3414
3415 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
3416  *
3417  * As a special case, we first check if there is any pair of constraints,
3418  * shared by all the basic maps in "map" that force a given dimension
3419  * to be equal to the floor of some affine combination of the input dimensions.
3420  *
3421  * In particular, if we can find two constraints
3422  *
3423  *      e(...) + c1 - m x >= 0          i.e.,           m x <= e(...) + c1
3424  *
3425  * and
3426  *
3427  *      -e(...) + c2 + m x >= 0         i.e.,           m x >= e(...) - c2
3428  *
3429  * where m > 1 and e only depends on parameters and input dimemnsions,
3430  * and such that
3431  *
3432  *      c1 + c2 < m                     i.e.,           -c2 >= c1 - (m - 1)
3433  *
3434  * then we know that we can take
3435  *
3436  *      x = floor((e(...) + c1) / m)
3437  *
3438  * without having to perform any computation.
3439  *
3440  * Note that we know that
3441  *
3442  *      c1 + c2 >= 1
3443  *
3444  * If c1 + c2 were 0, then we would have detected an equality during
3445  * simplification.  If c1 + c2 were negative, then we would have detected
3446  * a contradiction.
3447  */
3448 static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_check_div(
3449         __isl_take isl_map *map)
3450 {
3451         int d, dim;
3452         int i, j, n;
3453         int offset, total;
3454         isl_int sum;
3455         isl_basic_map *hull;
3456
3457         hull = isl_map_unshifted_simple_hull(isl_map_copy(map));
3458         if (!hull)
3459                 goto error;
3460
3461         isl_int_init(sum);
3462         dim = isl_map_dim(map, isl_dim_out);
3463         offset = isl_basic_map_offset(hull, isl_dim_out);
3464         total = 1 + isl_basic_map_total_dim(hull);
3465         n = hull->n_ineq;
3466         for (d = 0; d < dim; ++d) {
3467                 for (i = 0; i < n; ++i) {
3468                         if (!is_potential_div_constraint(hull->ineq[i],
3469                                                         offset, d, total))
3470                                 continue;
3471                         for (j = i + 1; j < n; ++j) {
3472                                 if (!isl_seq_is_neg(hull->ineq[i] + 1,
3473                                                 hull->ineq[j] + 1, total - 1))
3474                                         continue;
3475                                 isl_int_add(sum, hull->ineq[i][0],
3476                                                 hull->ineq[j][0]);
3477                                 if (isl_int_abs_lt(sum,
3478                                                     hull->ineq[i][offset + d]))
3479                                         break;
3480
3481                         }
3482                         if (j >= n)
3483                                 continue;
3484                         isl_int_clear(sum);
3485                         if (isl_int_is_pos(hull->ineq[j][offset + d]))
3486                                 j = i;
3487                         return pw_multi_aff_from_map_div(map, hull, d, j);
3488                 }
3489         }
3490         isl_int_clear(sum);
3491         isl_basic_map_free(hull);
3492         return pw_multi_aff_from_map_base(map);
3493 error:
3494         isl_map_free(map);
3495         isl_basic_map_free(hull);
3496         return NULL;
3497 }
3498
3499 /* Given an affine expression
3500  *
3501  *      [A -> B] -> f(A,B)
3502  *
3503  * construct an isl_multi_aff
3504  *
3505  *      [A -> B] -> B'
3506  *
3507  * such that dimension "d" in B' is set to "aff" and the remaining
3508  * dimensions are set equal to the corresponding dimensions in B.
3509  * "n_in" is the dimension of the space A.
3510  * "n_out" is the dimension of the space B.
3511  *
3512  * If "is_set" is set, then the affine expression is of the form
3513  *
3514  *      [B] -> f(B)
3515  *
3516  * and we construct an isl_multi_aff
3517  *
3518  *      B -> B'
3519  */
3520 static __isl_give isl_multi_aff *range_map(__isl_take isl_aff *aff, int d,
3521         unsigned n_in, unsigned n_out, int is_set)
3522 {
3523         int i;
3524         isl_multi_aff *ma;
3525         isl_space *space, *space2;
3526         isl_local_space *ls;
3527
3528         space = isl_aff_get_domain_space(aff);
3529         ls = isl_local_space_from_space(isl_space_copy(space));
3530         space2 = isl_space_copy(space);
3531         if (!is_set)
3532                 space2 = isl_space_range(isl_space_unwrap(space2));
3533         space = isl_space_map_from_domain_and_range(space, space2);
3534         ma = isl_multi_aff_alloc(space);
3535         ma = isl_multi_aff_set_aff(ma, d, aff);
3536
3537         for (i = 0; i < n_out; ++i) {
3538                 if (i == d)
3539                         continue;
3540                 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
3541                                                 isl_dim_set, n_in + i);
3542                 ma = isl_multi_aff_set_aff(ma, i, aff);
3543         }
3544
3545         isl_local_space_free(ls);
3546
3547         return ma;
3548 }
3549
3550 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
3551  * taking into account that the dimension at position "d" can be written as
3552  *
3553  *      x = m a + f(..)                                         (1)
3554  *
3555  * where m is equal to "gcd".
3556  * "i" is the index of the equality in "hull" that defines f(..).
3557  * In particular, the equality is of the form
3558  *
3559  *      f(..) - x + m g(existentials) = 0
3560  *
3561  * or
3562  *
3563  *      -f(..) + x + m g(existentials) = 0
3564  *
3565  * We basically plug (1) into "map", resulting in a map with "a"
3566  * in the range instead of "x".  The corresponding isl_pw_multi_aff
3567  * defining "a" is then plugged back into (1) to obtain a definition fro "x".
3568  *
3569  * Specifically, given the input map
3570  *
3571  *      A -> B
3572  *
3573  * We first wrap it into a set
3574  *
3575  *      [A -> B]
3576  *
3577  * and define (1) on top of the corresponding space, resulting in "aff".
3578  * We use this to create an isl_multi_aff that maps the output position "d"
3579  * from "a" to "x", leaving all other (intput and output) dimensions unchanged.
3580  * We plug this into the wrapped map, unwrap the result and compute the
3581  * corresponding isl_pw_multi_aff.
3582  * The result is an expression
3583  *
3584  *      A -> T(A)
3585  *
3586  * We adjust that to
3587  *
3588  *      A -> [A -> T(A)]
3589  *
3590  * so that we can plug that into "aff", after extending the latter to
3591  * a mapping
3592  *
3593  *      [A -> B] -> B'
3594  *
3595  *
3596  * If "map" is actually a set, then there is no "A" space, meaning
3597  * that we do not need to perform any wrapping, and that the result
3598  * of the recursive call is of the form
3599  *
3600  *      [T]
3601  *
3602  * which is plugged into a mapping of the form
3603  *
3604  *      B -> B'
3605  */
3606 static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_stride(
3607         __isl_take isl_map *map, __isl_take isl_basic_map *hull, int d, int i,
3608         isl_int gcd)
3609 {
3610         isl_set *set;
3611         isl_space *space;
3612         isl_local_space *ls;
3613         isl_aff *aff;
3614         isl_multi_aff *ma;
3615         isl_pw_multi_aff *pma, *id;
3616         unsigned n_in;
3617         unsigned o_out;
3618         unsigned n_out;
3619         int is_set;
3620
3621         is_set = isl_map_is_set(map);
3622
3623         n_in = isl_basic_map_dim(hull, isl_dim_in);
3624         n_out = isl_basic_map_dim(hull, isl_dim_out);
3625         o_out = isl_basic_map_offset(hull, isl_dim_out);
3626
3627         if (is_set)
3628                 set = map;
3629         else
3630                 set = isl_map_wrap(map);
3631         space = isl_space_map_from_set(isl_set_get_space(set));
3632         ma = isl_multi_aff_identity(space);
3633         ls = isl_local_space_from_space(isl_set_get_space(set));
3634         aff = isl_aff_alloc(ls);
3635         if (aff) {
3636                 isl_int_set_si(aff->v->el[0], 1);
3637                 if (isl_int_is_one(hull->eq[i][o_out + d]))
3638                         isl_seq_neg(aff->v->el + 1, hull->eq[i],
3639                                     aff->v->size - 1);
3640                 else
3641                         isl_seq_cpy(aff->v->el + 1, hull->eq[i],
3642                                     aff->v->size - 1);
3643                 isl_int_set(aff->v->el[1 + o_out + d], gcd);
3644         }
3645         ma = isl_multi_aff_set_aff(ma, n_in + d, isl_aff_copy(aff));
3646         set = isl_set_preimage_multi_aff(set, ma);
3647
3648         ma = range_map(aff, d, n_in, n_out, is_set);
3649
3650         if (is_set)
3651                 map = set;
3652         else
3653                 map = isl_set_unwrap(set);
3654         pma = isl_pw_multi_aff_from_map(set);
3655
3656         if (!is_set) {
3657                 space = isl_pw_multi_aff_get_domain_space(pma);
3658                 space = isl_space_map_from_set(space);
3659                 id = isl_pw_multi_aff_identity(space);
3660                 pma = isl_pw_multi_aff_range_product(id, pma);
3661         }
3662         id = isl_pw_multi_aff_from_multi_aff(ma);
3663         pma = isl_pw_multi_aff_pullback_pw_multi_aff(id, pma);
3664
3665         isl_basic_map_free(hull);
3666         return pma;
3667 }
3668
3669 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
3670  *
3671  * As a special case, we first check if all output dimensions are uniquely
3672  * defined in terms of the parameters and input dimensions over the entire
3673  * domain.  If so, we extract the desired isl_pw_multi_aff directly
3674  * from the affine hull of "map" and its domain.
3675  *
3676  * Otherwise, we check if any of the output dimensions is "strided".
3677  * That is, we check if can be written as
3678  *
3679  *      x = m a + f(..)
3680  *
3681  * with m greater than 1, a some combination of existentiall quantified
3682  * variables and f and expression in the parameters and input dimensions.
3683  * If so, we remove the stride in pw_multi_aff_from_map_stride.
3684  *
3685  * Otherwise, we continue with pw_multi_aff_from_map_check_div for a further
3686  * special case.
3687  */
3688 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_map(__isl_take isl_map *map)
3689 {
3690         int i, j;
3691         int sv;
3692         isl_basic_map *hull;
3693         unsigned n_out;
3694         unsigned o_out;
3695         unsigned n_div;
3696         unsigned o_div;
3697         isl_int gcd;
3698
3699         if (!map)
3700                 return NULL;
3701
3702         hull = isl_map_affine_hull(isl_map_copy(map));
3703         sv = isl_basic_map_plain_is_single_valued(hull);
3704         if (sv >= 0 && sv)
3705                 return plain_pw_multi_aff_from_map(isl_map_domain(map), hull);
3706         if (sv < 0)
3707                 hull = isl_basic_map_free(hull);
3708         if (!hull)
3709                 goto error;
3710
3711         n_div = isl_basic_map_dim(hull, isl_dim_div);
3712         o_div = isl_basic_map_offset(hull, isl_dim_div);
3713
3714         if (n_div == 0) {
3715                 isl_basic_map_free(hull);
3716                 return pw_multi_aff_from_map_check_div(map);
3717         }
3718
3719         isl_int_init(gcd);
3720
3721         n_out = isl_basic_map_dim(hull, isl_dim_out);
3722         o_out = isl_basic_map_offset(hull, isl_dim_out);
3723
3724         for (i = 0; i < n_out; ++i) {
3725                 for (j = 0; j < hull->n_eq; ++j) {
3726                         isl_int *eq = hull->eq[j];
3727                         isl_pw_multi_aff *res;
3728
3729                         if (!isl_int_is_one(eq[o_out + i]) &&
3730                             !isl_int_is_negone(eq[o_out + i]))
3731                                 continue;
3732                         if (isl_seq_first_non_zero(eq + o_out, i) != -1)
3733                                 continue;
3734                         if (isl_seq_first_non_zero(eq + o_out + i + 1,
3735                                                     n_out - (i + 1)) != -1)
3736                                 continue;
3737                         isl_seq_gcd(eq + o_div, n_div, &gcd);
3738                         if (isl_int_is_zero(gcd))
3739                                 continue;
3740                         if (isl_int_is_one(gcd))
3741                                 continue;
3742
3743                         res = pw_multi_aff_from_map_stride(map, hull,
3744                                                                 i, j, gcd);
3745                         isl_int_clear(gcd);
3746                         return res;
3747                 }
3748         }
3749
3750         isl_int_clear(gcd);
3751         isl_basic_map_free(hull);
3752         return pw_multi_aff_from_map_check_div(map);
3753 error:
3754         isl_map_free(map);
3755         return NULL;
3756 }
3757
3758 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_set(__isl_take isl_set *set)
3759 {
3760         return isl_pw_multi_aff_from_map(set);
3761 }
3762
3763 /* Return the piecewise affine expression "set ? 1 : 0".
3764  */
3765 __isl_give isl_pw_aff *isl_set_indicator_function(__isl_take isl_set *set)
3766 {
3767         isl_pw_aff *pa;
3768         isl_space *space = isl_set_get_space(set);
3769         isl_local_space *ls = isl_local_space_from_space(space);
3770         isl_aff *zero = isl_aff_zero_on_domain(isl_local_space_copy(ls));
3771         isl_aff *one = isl_aff_zero_on_domain(ls);
3772
3773         one = isl_aff_add_constant_si(one, 1);
3774         pa = isl_pw_aff_alloc(isl_set_copy(set), one);
3775         set = isl_set_complement(set);
3776         pa = isl_pw_aff_add_disjoint(pa, isl_pw_aff_alloc(set, zero));
3777
3778         return pa;
3779 }
3780
3781 /* Plug in "subs" for dimension "type", "pos" of "aff".
3782  *
3783  * Let i be the dimension to replace and let "subs" be of the form
3784  *
3785  *      f/d
3786  *
3787  * and "aff" of the form
3788  *
3789  *      (a i + g)/m
3790  *
3791  * The result is
3792  *
3793  *      (a f + d g')/(m d)
3794  *
3795  * where g' is the result of plugging in "subs" in each of the integer
3796  * divisions in g.
3797  */
3798 __isl_give isl_aff *isl_aff_substitute(__isl_take isl_aff *aff,
3799         enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs)
3800 {
3801         isl_ctx *ctx;
3802         isl_int v;
3803
3804         aff = isl_aff_cow(aff);
3805         if (!aff || !subs)
3806                 return isl_aff_free(aff);
3807
3808         ctx = isl_aff_get_ctx(aff);
3809         if (!isl_space_is_equal(aff->ls->dim, subs->ls->dim))
3810                 isl_die(ctx, isl_error_invalid,
3811                         "spaces don't match", return isl_aff_free(aff));
3812         if (isl_local_space_dim(subs->ls, isl_dim_div) != 0)
3813                 isl_die(ctx, isl_error_unsupported,
3814                         "cannot handle divs yet", return isl_aff_free(aff));
3815
3816         aff->ls = isl_local_space_substitute(aff->ls, type, pos, subs);
3817         if (!aff->ls)
3818                 return isl_aff_free(aff);
3819
3820         aff->v = isl_vec_cow(aff->v);
3821         if (!aff->v)
3822                 return isl_aff_free(aff);
3823
3824         pos += isl_local_space_offset(aff->ls, type);
3825
3826         isl_int_init(v);
3827         isl_seq_substitute(aff->v->el, pos, subs->v->el,
3828                             aff->v->size, subs->v->size, v);
3829         isl_int_clear(v);
3830
3831         return aff;
3832 }
3833
3834 /* Plug in "subs" for dimension "type", "pos" in each of the affine
3835  * expressions in "maff".
3836  */
3837 __isl_give isl_multi_aff *isl_multi_aff_substitute(
3838         __isl_take isl_multi_aff *maff, enum isl_dim_type type, unsigned pos,
3839         __isl_keep isl_aff *subs)
3840 {
3841         int i;
3842
3843         maff = isl_multi_aff_cow(maff);
3844         if (!maff || !subs)
3845                 return isl_multi_aff_free(maff);
3846
3847         if (type == isl_dim_in)
3848                 type = isl_dim_set;
3849
3850         for (i = 0; i < maff->n; ++i) {
3851                 maff->p[i] = isl_aff_substitute(maff->p[i], type, pos, subs);
3852                 if (!maff->p[i])
3853                         return isl_multi_aff_free(maff);
3854         }
3855
3856         return maff;
3857 }
3858
3859 /* Plug in "subs" for dimension "type", "pos" of "pma".
3860  *
3861  * pma is of the form
3862  *
3863  *      A_i(v) -> M_i(v)
3864  *
3865  * while subs is of the form
3866  *
3867  *      v' = B_j(v) -> S_j
3868  *
3869  * Each pair i,j such that C_ij = A_i \cap B_i is non-empty
3870  * has a contribution in the result, in particular
3871  *
3872  *      C_ij(S_j) -> M_i(S_j)
3873  *
3874  * Note that plugging in S_j in C_ij may also result in an empty set
3875  * and this contribution should simply be discarded.
3876  */
3877 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_substitute(
3878         __isl_take isl_pw_multi_aff *pma, enum isl_dim_type type, unsigned pos,
3879         __isl_keep isl_pw_aff *subs)
3880 {
3881         int i, j, n;
3882         isl_pw_multi_aff *res;
3883
3884         if (!pma || !subs)
3885                 return isl_pw_multi_aff_free(pma);
3886
3887         n = pma->n * subs->n;
3888         res = isl_pw_multi_aff_alloc_size(isl_space_copy(pma->dim), n);
3889
3890         for (i = 0; i < pma->n; ++i) {
3891                 for (j = 0; j < subs->n; ++j) {
3892                         isl_set *common;
3893                         isl_multi_aff *res_ij;
3894                         int empty;
3895
3896                         common = isl_set_intersect(
3897                                         isl_set_copy(pma->p[i].set),
3898                                         isl_set_copy(subs->p[j].set));
3899                         common = isl_set_substitute(common,
3900                                         type, pos, subs->p[j].aff);
3901                         empty = isl_set_plain_is_empty(common);
3902                         if (empty < 0 || empty) {
3903                                 isl_set_free(common);
3904                                 if (empty < 0)
3905                                         goto error;
3906                                 continue;
3907                         }
3908
3909                         res_ij = isl_multi_aff_substitute(
3910                                         isl_multi_aff_copy(pma->p[i].maff),
3911                                         type, pos, subs->p[j].aff);
3912
3913                         res = isl_pw_multi_aff_add_piece(res, common, res_ij);
3914                 }
3915         }
3916
3917         isl_pw_multi_aff_free(pma);
3918         return res;
3919 error:
3920         isl_pw_multi_aff_free(pma);
3921         isl_pw_multi_aff_free(res);
3922         return NULL;
3923 }
3924
3925 /* Compute the preimage of the affine expression "src" under "ma"
3926  * and put the result in "dst".  If "has_denom" is set (to one),
3927  * then "src" and "dst" have an extra initial denominator.
3928  * "n_div_ma" is the number of existentials in "ma"
3929  * "n_div_bset" is the number of existentials in "src"
3930  * The resulting "dst" (which is assumed to have been allocated by
3931  * the caller) contains coefficients for both sets of existentials,
3932  * first those in "ma" and then those in "src".
3933  * f, c1, c2 and g are temporary objects that have been initialized
3934  * by the caller.
3935  *
3936  * Let src represent the expression
3937  *
3938  *      (a(p) + b x + c(divs))/d
3939  *
3940  * and let ma represent the expressions
3941  *
3942  *      x_i = (r_i(p) + s_i(y) + t_i(divs'))/m_i
3943  *
3944  * We start out with the following expression for dst:
3945  *
3946  *      (a(p) + 0 y + 0 divs' + f \sum_i b_i x_i + c(divs))/d
3947  *
3948  * with the multiplication factor f initially equal to 1.
3949  * For each x_i that we substitute, we multiply the numerator
3950  * (and denominator) of dst by c_1 = m_i and add the numerator
3951  * of the x_i expression multiplied by c_2 = f b_i,
3952  * after removing the common factors of c_1 and c_2.
3953  * The multiplication factor f also needs to be multiplied by c_1
3954  * for the next x_j, j > i.
3955  */
3956 void isl_seq_preimage(isl_int *dst, isl_int *src,
3957         __isl_keep isl_multi_aff *ma, int n_div_ma, int n_div_bset,
3958         isl_int f, isl_int c1, isl_int c2, isl_int g, int has_denom)
3959 {
3960         int i;
3961         int n_param, n_in, n_out;
3962         int o_div_bset;
3963
3964         n_param = isl_multi_aff_dim(ma, isl_dim_param);
3965         n_in = isl_multi_aff_dim(ma, isl_dim_in);
3966         n_out = isl_multi_aff_dim(ma, isl_dim_out);
3967
3968         o_div_bset = has_denom + 1 + n_param + n_in + n_div_ma;
3969
3970         isl_seq_cpy(dst, src, has_denom + 1 + n_param);
3971         isl_seq_clr(dst + has_denom + 1 + n_param, n_in + n_div_ma);
3972         isl_seq_cpy(dst + o_div_bset,
3973                     src + has_denom + 1 + n_param + n_out, n_div_bset);
3974
3975         isl_int_set_si(f, 1);
3976
3977         for (i = 0; i < n_out; ++i) {
3978                 if (isl_int_is_zero(src[has_denom + 1 + n_param + i]))
3979                         continue;
3980                 isl_int_set(c1, ma->p[i]->v->el[0]);
3981                 isl_int_mul(c2, f, src[has_denom + 1 + n_param + i]);
3982                 isl_int_gcd(g, c1, c2);
3983                 isl_int_divexact(c1, c1, g);
3984                 isl_int_divexact(c2, c2, g);
3985
3986                 isl_int_mul(f, f, c1);
3987                 isl_seq_combine(dst + has_denom, c1, dst + has_denom,
3988                                 c2, ma->p[i]->v->el + 1, ma->p[i]->v->size - 1);
3989                 isl_seq_scale(dst + o_div_bset,
3990                                 dst + o_div_bset, c1, n_div_bset);
3991                 if (has_denom)
3992                         isl_int_mul(dst[0], dst[0], c1);
3993         }
3994 }
3995
3996 /* Compute the pullback of "aff" by the function represented by "ma".
3997  * In other words, plug in "ma" in "aff".  The result is an affine expression
3998  * defined over the domain space of "ma".
3999  *
4000  * If "aff" is represented by
4001  *
4002  *      (a(p) + b x + c(divs))/d
4003  *
4004  * and ma is represented by
4005  *
4006  *      x = D(p) + F(y) + G(divs')
4007  *
4008  * then the result is
4009  *
4010  *      (a(p) + b D(p) + b F(y) + b G(divs') + c(divs))/d
4011  *
4012  * The divs in the local space of the input are similarly adjusted
4013  * through a call to isl_local_space_preimage_multi_aff.
4014  */
4015 __isl_give isl_aff *isl_aff_pullback_multi_aff(__isl_take isl_aff *aff,
4016         __isl_take isl_multi_aff *ma)
4017 {
4018         isl_aff *res = NULL;
4019         isl_local_space *ls;
4020         int n_div_aff, n_div_ma;
4021         isl_int f, c1, c2, g;
4022
4023         ma = isl_multi_aff_align_divs(ma);
4024         if (!aff || !ma)
4025                 goto error;
4026
4027         n_div_aff = isl_aff_dim(aff, isl_dim_div);
4028         n_div_ma = ma->n ? isl_aff_dim(ma->p[0], isl_dim_div) : 0;
4029
4030         ls = isl_aff_get_domain_local_space(aff);
4031         ls = isl_local_space_preimage_multi_aff(ls, isl_multi_aff_copy(ma));
4032         res = isl_aff_alloc(ls);
4033         if (!res)
4034                 goto error;
4035
4036         isl_int_init(f);
4037         isl_int_init(c1);
4038         isl_int_init(c2);
4039         isl_int_init(g);
4040
4041         isl_seq_preimage(res->v->el, aff->v->el, ma, n_div_ma, n_div_aff,
4042                         f, c1, c2, g, 1);
4043
4044         isl_int_clear(f);
4045         isl_int_clear(c1);
4046         isl_int_clear(c2);
4047         isl_int_clear(g);
4048
4049         isl_aff_free(aff);
4050         isl_multi_aff_free(ma);
4051         res = isl_aff_normalize(res);
4052         return res;
4053 error:
4054         isl_aff_free(aff);
4055         isl_multi_aff_free(ma);
4056         isl_aff_free(res);
4057         return NULL;
4058 }
4059
4060 /* Compute the pullback of "ma1" by the function represented by "ma2".
4061  * In other words, plug in "ma2" in "ma1".
4062  */
4063 __isl_give isl_multi_aff *isl_multi_aff_pullback_multi_aff(
4064         __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2)
4065 {
4066         int i;
4067         isl_space *space = NULL;
4068
4069         ma2 = isl_multi_aff_align_divs(ma2);
4070         ma1 = isl_multi_aff_cow(ma1);
4071         if (!ma1 || !ma2)
4072                 goto error;
4073
4074         space = isl_space_join(isl_multi_aff_get_space(ma2),
4075                                 isl_multi_aff_get_space(ma1));
4076
4077         for (i = 0; i < ma1->n; ++i) {
4078                 ma1->p[i] = isl_aff_pullback_multi_aff(ma1->p[i],
4079                                                     isl_multi_aff_copy(ma2));
4080                 if (!ma1->p[i])
4081                         goto error;
4082         }
4083
4084         ma1 = isl_multi_aff_reset_space(ma1, space);
4085         isl_multi_aff_free(ma2);
4086         return ma1;
4087 error:
4088         isl_space_free(space);
4089         isl_multi_aff_free(ma2);
4090         isl_multi_aff_free(ma1);
4091         return NULL;
4092 }
4093
4094 /* Extend the local space of "dst" to include the divs
4095  * in the local space of "src".
4096  */
4097 __isl_give isl_aff *isl_aff_align_divs(__isl_take isl_aff *dst,
4098         __isl_keep isl_aff *src)
4099 {
4100         isl_ctx *ctx;
4101         int *exp1 = NULL;
4102         int *exp2 = NULL;
4103         isl_mat *div;
4104
4105         if (!src || !dst)
4106                 return isl_aff_free(dst);
4107
4108         ctx = isl_aff_get_ctx(src);
4109         if (!isl_space_is_equal(src->ls->dim, dst->ls->dim))
4110                 isl_die(ctx, isl_error_invalid,
4111                         "spaces don't match", goto error);
4112
4113         if (src->ls->div->n_row == 0)
4114                 return dst;
4115
4116         exp1 = isl_alloc_array(ctx, int, src->ls->div->n_row);
4117         exp2 = isl_alloc_array(ctx, int, dst->ls->div->n_row);
4118         if (!exp1 || !exp2)
4119                 goto error;
4120
4121         div = isl_merge_divs(src->ls->div, dst->ls->div, exp1, exp2);
4122         dst = isl_aff_expand_divs(dst, div, exp2);
4123         free(exp1);
4124         free(exp2);
4125
4126         return dst;
4127 error:
4128         free(exp1);
4129         free(exp2);
4130         return isl_aff_free(dst);
4131 }
4132
4133 /* Adjust the local spaces of the affine expressions in "maff"
4134  * such that they all have the save divs.
4135  */
4136 __isl_give isl_multi_aff *isl_multi_aff_align_divs(
4137         __isl_take isl_multi_aff *maff)
4138 {
4139         int i;
4140
4141         if (!maff)
4142                 return NULL;
4143         if (maff->n == 0)
4144                 return maff;
4145         maff = isl_multi_aff_cow(maff);
4146         if (!maff)
4147                 return NULL;
4148
4149         for (i = 1; i < maff->n; ++i)
4150                 maff->p[0] = isl_aff_align_divs(maff->p[0], maff->p[i]);
4151         for (i = 1; i < maff->n; ++i) {
4152                 maff->p[i] = isl_aff_align_divs(maff->p[i], maff->p[0]);
4153                 if (!maff->p[i])
4154                         return isl_multi_aff_free(maff);
4155         }
4156
4157         return maff;
4158 }
4159
4160 __isl_give isl_aff *isl_aff_lift(__isl_take isl_aff *aff)
4161 {
4162         aff = isl_aff_cow(aff);
4163         if (!aff)
4164                 return NULL;
4165
4166         aff->ls = isl_local_space_lift(aff->ls);
4167         if (!aff->ls)
4168                 return isl_aff_free(aff);
4169
4170         return aff;
4171 }
4172
4173 /* Lift "maff" to a space with extra dimensions such that the result
4174  * has no more existentially quantified variables.
4175  * If "ls" is not NULL, then *ls is assigned the local space that lies
4176  * at the basis of the lifting applied to "maff".
4177  */
4178 __isl_give isl_multi_aff *isl_multi_aff_lift(__isl_take isl_multi_aff *maff,
4179         __isl_give isl_local_space **ls)
4180 {
4181         int i;
4182         isl_space *space;
4183         unsigned n_div;
4184
4185         if (ls)
4186                 *ls = NULL;
4187
4188         if (!maff)
4189                 return NULL;
4190
4191         if (maff->n == 0) {
4192                 if (ls) {
4193                         isl_space *space = isl_multi_aff_get_domain_space(maff);
4194                         *ls = isl_local_space_from_space(space);
4195                         if (!*ls)
4196                                 return isl_multi_aff_free(maff);
4197                 }
4198                 return maff;
4199         }
4200
4201         maff = isl_multi_aff_cow(maff);
4202         maff = isl_multi_aff_align_divs(maff);
4203         if (!maff)
4204                 return NULL;
4205
4206         n_div = isl_aff_dim(maff->p[0], isl_dim_div);
4207         space = isl_multi_aff_get_space(maff);
4208         space = isl_space_lift(isl_space_domain(space), n_div);
4209         space = isl_space_extend_domain_with_range(space,
4210                                                 isl_multi_aff_get_space(maff));
4211         if (!space)
4212                 return isl_multi_aff_free(maff);
4213         isl_space_free(maff->space);
4214         maff->space = space;
4215
4216         if (ls) {
4217                 *ls = isl_aff_get_domain_local_space(maff->p[0]);
4218                 if (!*ls)
4219                         return isl_multi_aff_free(maff);
4220         }
4221
4222         for (i = 0; i < maff->n; ++i) {
4223                 maff->p[i] = isl_aff_lift(maff->p[i]);
4224                 if (!maff->p[i])
4225                         goto error;
4226         }
4227
4228         return maff;
4229 error:
4230         if (ls)
4231                 isl_local_space_free(*ls);
4232         return isl_multi_aff_free(maff);
4233 }
4234
4235
4236 /* Extract an isl_pw_aff corresponding to output dimension "pos" of "pma".
4237  */
4238 __isl_give isl_pw_aff *isl_pw_multi_aff_get_pw_aff(
4239         __isl_keep isl_pw_multi_aff *pma, int pos)
4240 {
4241         int i;
4242         int n_out;
4243         isl_space *space;
4244         isl_pw_aff *pa;
4245
4246         if (!pma)
4247                 return NULL;
4248
4249         n_out = isl_pw_multi_aff_dim(pma, isl_dim_out);
4250         if (pos < 0 || pos >= n_out)
4251                 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
4252                         "index out of bounds", return NULL);
4253
4254         space = isl_pw_multi_aff_get_space(pma);
4255         space = isl_space_drop_dims(space, isl_dim_out,
4256                                     pos + 1, n_out - pos - 1);
4257         space = isl_space_drop_dims(space, isl_dim_out, 0, pos);
4258
4259         pa = isl_pw_aff_alloc_size(space, pma->n);
4260         for (i = 0; i < pma->n; ++i) {
4261                 isl_aff *aff;
4262                 aff = isl_multi_aff_get_aff(pma->p[i].maff, pos);
4263                 pa = isl_pw_aff_add_piece(pa, isl_set_copy(pma->p[i].set), aff);
4264         }
4265
4266         return pa;
4267 }
4268
4269 /* Return an isl_pw_multi_aff with the given "set" as domain and
4270  * an unnamed zero-dimensional range.
4271  */
4272 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_domain(
4273         __isl_take isl_set *set)
4274 {
4275         isl_multi_aff *ma;
4276         isl_space *space;
4277
4278         space = isl_set_get_space(set);
4279         space = isl_space_from_domain(space);
4280         ma = isl_multi_aff_zero(space);
4281         return isl_pw_multi_aff_alloc(set, ma);
4282 }
4283
4284 /* Add an isl_pw_multi_aff with the given "set" as domain and
4285  * an unnamed zero-dimensional range to *user.
4286  */
4287 static int add_pw_multi_aff_from_domain(__isl_take isl_set *set, void *user)
4288 {
4289         isl_union_pw_multi_aff **upma = user;
4290         isl_pw_multi_aff *pma;
4291
4292         pma = isl_pw_multi_aff_from_domain(set);
4293         *upma = isl_union_pw_multi_aff_add_pw_multi_aff(*upma, pma);
4294
4295         return 0;
4296 }
4297
4298 /* Return an isl_union_pw_multi_aff with the given "uset" as domain and
4299  * an unnamed zero-dimensional range.
4300  */
4301 __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_from_domain(
4302         __isl_take isl_union_set *uset)
4303 {
4304         isl_space *space;
4305         isl_union_pw_multi_aff *upma;
4306
4307         if (!uset)
4308                 return NULL;
4309
4310         space = isl_union_set_get_space(uset);
4311         upma = isl_union_pw_multi_aff_empty(space);
4312
4313         if (isl_union_set_foreach_set(uset,
4314                                     &add_pw_multi_aff_from_domain, &upma) < 0)
4315                 goto error;
4316
4317         isl_union_set_free(uset);
4318         return upma;
4319 error:
4320         isl_union_set_free(uset);
4321         isl_union_pw_multi_aff_free(upma);
4322         return NULL;
4323 }
4324
4325 /* Convert "pma" to an isl_map and add it to *umap.
4326  */
4327 static int map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma, void *user)
4328 {
4329         isl_union_map **umap = user;
4330         isl_map *map;
4331
4332         map = isl_map_from_pw_multi_aff(pma);
4333         *umap = isl_union_map_add_map(*umap, map);
4334
4335         return 0;
4336 }
4337
4338 /* Construct a union map mapping the domain of the union
4339  * piecewise multi-affine expression to its range, with each dimension
4340  * in the range equated to the corresponding affine expression on its cell.
4341  */
4342 __isl_give isl_union_map *isl_union_map_from_union_pw_multi_aff(
4343         __isl_take isl_union_pw_multi_aff *upma)
4344 {
4345         isl_space *space;
4346         isl_union_map *umap;
4347
4348         if (!upma)
4349                 return NULL;
4350
4351         space = isl_union_pw_multi_aff_get_space(upma);
4352         umap = isl_union_map_empty(space);
4353
4354         if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma,
4355                                         &map_from_pw_multi_aff, &umap) < 0)
4356                 goto error;
4357
4358         isl_union_pw_multi_aff_free(upma);
4359         return umap;
4360 error:
4361         isl_union_pw_multi_aff_free(upma);
4362         isl_union_map_free(umap);
4363         return NULL;
4364 }
4365
4366 /* Local data for bin_entry and the callback "fn".
4367  */
4368 struct isl_union_pw_multi_aff_bin_data {
4369         isl_union_pw_multi_aff *upma2;
4370         isl_union_pw_multi_aff *res;
4371         isl_pw_multi_aff *pma;
4372         int (*fn)(void **entry, void *user);
4373 };
4374
4375 /* Given an isl_pw_multi_aff from upma1, store it in data->pma
4376  * and call data->fn for each isl_pw_multi_aff in data->upma2.
4377  */
4378 static int bin_entry(void **entry, void *user)
4379 {
4380         struct isl_union_pw_multi_aff_bin_data *data = user;
4381         isl_pw_multi_aff *pma = *entry;
4382
4383         data->pma = pma;
4384         if (isl_hash_table_foreach(data->upma2->dim->ctx, &data->upma2->table,
4385                                    data->fn, data) < 0)
4386                 return -1;
4387
4388         return 0;
4389 }
4390
4391 /* Call "fn" on each pair of isl_pw_multi_affs in "upma1" and "upma2".
4392  * The isl_pw_multi_aff from upma1 is stored in data->pma (where data is
4393  * passed as user field) and the isl_pw_multi_aff from upma2 is available
4394  * as *entry.  The callback should adjust data->res if desired.
4395  */
4396 static __isl_give isl_union_pw_multi_aff *bin_op(
4397         __isl_take isl_union_pw_multi_aff *upma1,
4398         __isl_take isl_union_pw_multi_aff *upma2,
4399         int (*fn)(void **entry, void *user))
4400 {
4401         isl_space *space;
4402         struct isl_union_pw_multi_aff_bin_data data = { NULL, NULL, NULL, fn };
4403
4404         space = isl_union_pw_multi_aff_get_space(upma2);
4405         upma1 = isl_union_pw_multi_aff_align_params(upma1, space);
4406         space = isl_union_pw_multi_aff_get_space(upma1);
4407         upma2 = isl_union_pw_multi_aff_align_params(upma2, space);
4408
4409         if (!upma1 || !upma2)
4410                 goto error;
4411
4412         data.upma2 = upma2;
4413         data.res = isl_union_pw_multi_aff_alloc(isl_space_copy(upma1->dim),
4414                                        upma1->table.n);
4415         if (isl_hash_table_foreach(upma1->dim->ctx, &upma1->table,
4416                                    &bin_entry, &data) < 0)
4417                 goto error;
4418
4419         isl_union_pw_multi_aff_free(upma1);
4420         isl_union_pw_multi_aff_free(upma2);
4421         return data.res;
4422 error:
4423         isl_union_pw_multi_aff_free(upma1);
4424         isl_union_pw_multi_aff_free(upma2);
4425         isl_union_pw_multi_aff_free(data.res);
4426         return NULL;
4427 }
4428
4429 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
4430  * construct an isl_pw_multi_aff (A * C) -> [B -> D].
4431  */
4432 static __isl_give isl_pw_multi_aff *pw_multi_aff_range_product(
4433         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4434 {
4435         isl_space *space;
4436
4437         space = isl_space_range_product(isl_pw_multi_aff_get_space(pma1),
4438                                         isl_pw_multi_aff_get_space(pma2));
4439         return isl_pw_multi_aff_on_shared_domain_in(pma1, pma2, space,
4440                                             &isl_multi_aff_range_product);
4441 }
4442
4443 /* Given two isl_pw_multi_affs A -> B and C -> D,
4444  * construct an isl_pw_multi_aff (A * C) -> [B -> D].
4445  */
4446 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_range_product(
4447         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4448 {
4449         return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
4450                                             &pw_multi_aff_range_product);
4451 }
4452
4453 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
4454  * construct an isl_pw_multi_aff (A * C) -> (B, D).
4455  */
4456 static __isl_give isl_pw_multi_aff *pw_multi_aff_flat_range_product(
4457         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4458 {
4459         isl_space *space;
4460
4461         space = isl_space_range_product(isl_pw_multi_aff_get_space(pma1),
4462                                         isl_pw_multi_aff_get_space(pma2));
4463         space = isl_space_flatten_range(space);
4464         return isl_pw_multi_aff_on_shared_domain_in(pma1, pma2, space,
4465                                             &isl_multi_aff_flat_range_product);
4466 }
4467
4468 /* Given two isl_pw_multi_affs A -> B and C -> D,
4469  * construct an isl_pw_multi_aff (A * C) -> (B, D).
4470  */
4471 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_flat_range_product(
4472         __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4473 {
4474         return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
4475                                             &pw_multi_aff_flat_range_product);
4476 }
4477
4478 /* If data->pma and *entry have the same domain space, then compute
4479  * their flat range product and the result to data->res.
4480  */
4481 static int flat_range_product_entry(void **entry, void *user)
4482 {
4483         struct isl_union_pw_multi_aff_bin_data *data = user;
4484         isl_pw_multi_aff *pma2 = *entry;
4485
4486         if (!isl_space_tuple_match(data->pma->dim, isl_dim_in,
4487                                  pma2->dim, isl_dim_in))
4488                 return 0;
4489
4490         pma2 = isl_pw_multi_aff_flat_range_product(
4491                                         isl_pw_multi_aff_copy(data->pma),
4492                                         isl_pw_multi_aff_copy(pma2));
4493
4494         data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res, pma2);
4495
4496         return 0;
4497 }
4498
4499 /* Given two isl_union_pw_multi_affs A -> B and C -> D,
4500  * construct an isl_union_pw_multi_aff (A * C) -> (B, D).
4501  */
4502 __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_flat_range_product(
4503         __isl_take isl_union_pw_multi_aff *upma1,
4504         __isl_take isl_union_pw_multi_aff *upma2)
4505 {
4506         return bin_op(upma1, upma2, &flat_range_product_entry);
4507 }
4508
4509 /* Replace the affine expressions at position "pos" in "pma" by "pa".
4510  * The parameters are assumed to have been aligned.
4511  *
4512  * The implementation essentially performs an isl_pw_*_on_shared_domain,
4513  * except that it works on two different isl_pw_* types.
4514  */
4515 static __isl_give isl_pw_multi_aff *pw_multi_aff_set_pw_aff(
4516         __isl_take isl_pw_multi_aff *pma, unsigned pos,
4517         __isl_take isl_pw_aff *pa)
4518 {
4519         int i, j, n;
4520         isl_pw_multi_aff *res = NULL;
4521
4522         if (!pma || !pa)
4523                 goto error;
4524
4525         if (!isl_space_tuple_match(pma->dim, isl_dim_in, pa->dim, isl_dim_in))
4526                 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
4527                         "domains don't match", goto error);
4528         if (pos >= isl_pw_multi_aff_dim(pma, isl_dim_out))
4529                 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
4530                         "index out of bounds", goto error);
4531
4532         n = pma->n * pa->n;
4533         res = isl_pw_multi_aff_alloc_size(isl_pw_multi_aff_get_space(pma), n);
4534
4535         for (i = 0; i < pma->n; ++i) {
4536                 for (j = 0; j < pa->n; ++j) {
4537                         isl_set *common;
4538                         isl_multi_aff *res_ij;
4539                         int empty;
4540
4541                         common = isl_set_intersect(isl_set_copy(pma->p[i].set),
4542                                                    isl_set_copy(pa->p[j].set));
4543                         empty = isl_set_plain_is_empty(common);
4544                         if (empty < 0 || empty) {
4545                                 isl_set_free(common);
4546                                 if (empty < 0)
4547                                         goto error;
4548                                 continue;
4549                         }
4550
4551                         res_ij = isl_multi_aff_set_aff(
4552                                         isl_multi_aff_copy(pma->p[i].maff), pos,
4553                                         isl_aff_copy(pa->p[j].aff));
4554                         res_ij = isl_multi_aff_gist(res_ij,
4555                                         isl_set_copy(common));
4556
4557                         res = isl_pw_multi_aff_add_piece(res, common, res_ij);
4558                 }
4559         }
4560
4561         isl_pw_multi_aff_free(pma);
4562         isl_pw_aff_free(pa);
4563         return res;
4564 error:
4565         isl_pw_multi_aff_free(pma);
4566         isl_pw_aff_free(pa);
4567         return isl_pw_multi_aff_free(res);
4568 }
4569
4570 /* Replace the affine expressions at position "pos" in "pma" by "pa".
4571  */
4572 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_set_pw_aff(
4573         __isl_take isl_pw_multi_aff *pma, unsigned pos,
4574         __isl_take isl_pw_aff *pa)
4575 {
4576         if (!pma || !pa)
4577                 goto error;
4578         if (isl_space_match(pma->dim, isl_dim_param, pa->dim, isl_dim_param))
4579                 return pw_multi_aff_set_pw_aff(pma, pos, pa);
4580         if (!isl_space_has_named_params(pma->dim) ||
4581             !isl_space_has_named_params(pa->dim))
4582                 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
4583                         "unaligned unnamed parameters", goto error);
4584         pma = isl_pw_multi_aff_align_params(pma, isl_pw_aff_get_space(pa));
4585         pa = isl_pw_aff_align_params(pa, isl_pw_multi_aff_get_space(pma));
4586         return pw_multi_aff_set_pw_aff(pma, pos, pa);
4587 error:
4588         isl_pw_multi_aff_free(pma);
4589         isl_pw_aff_free(pa);
4590         return NULL;
4591 }
4592
4593 #undef BASE
4594 #define BASE pw_aff
4595
4596 #include <isl_multi_templ.c>