isl_aff.c

   1 /*
   2  * Copyright 2011      INRIA Saclay
   3  *
   4  * Use of this software is governed by the GNU LGPLv2.1 license
   5  *
   6  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   7  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   8  * 91893 Orsay, France
   9  */
  10
  11 #include <isl_map_private.h>
  12 #include <isl_aff_private.h>
  13 #include <isl_dim_private.h>
  14 #include <isl_local_space_private.h>
  15 #include <isl_mat_private.h>
  16 #include <isl/constraint.h>
  17 #include <isl/seq.h>
  18 #include <isl/set.h>
  19
  20 __isl_give isl_aff *isl_aff_alloc_vec(__isl_take isl_local_space *ls,
  21         __isl_take isl_vec *v)
  22 {
  23         isl_aff *aff;
  24
  25         if (!ls || !v)
  26                 goto error;
  27
  28         aff = isl_calloc_type(v->ctx, struct isl_aff);
  29         if (!aff)
  30                 goto error;
  31
  32         aff->ref = 1;
  33         aff->ls = ls;
  34         aff->v = v;
  35
  36         return aff;
  37 error:
  38         isl_local_space_free(ls);
  39         isl_vec_free(v);
  40         return NULL;
  41 }
  42
  43 __isl_give isl_aff *isl_aff_alloc(__isl_take isl_local_space *ls)
  44 {
  45         isl_ctx *ctx;
  46         isl_vec *v;
  47         unsigned total;
  48
  49         if (!ls)
  50                 return NULL;
  51
  52         ctx = isl_local_space_get_ctx(ls);
  53         if (!isl_local_space_divs_known(ls))
  54                 isl_die(ctx, isl_error_invalid, "local space has unknown divs",
  55                         goto error);
  56
  57         total = isl_local_space_dim(ls, isl_dim_all);
  58         v = isl_vec_alloc(ctx, 1 + 1 + total);
  59         return isl_aff_alloc_vec(ls, v);
  60 error:
  61         isl_local_space_free(ls);
  62         return NULL;
  63 }
  64
  65 __isl_give isl_aff *isl_aff_zero(__isl_take isl_local_space *ls)
  66 {
  67         isl_aff *aff;
  68
  69         aff = isl_aff_alloc(ls);
  70         if (!aff)
  71                 return NULL;
  72
  73         isl_int_set_si(aff->v->el[0], 1);
  74         isl_seq_clr(aff->v->el + 1, aff->v->size - 1);
  75
  76         return aff;
  77 }
  78
  79 __isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff)
  80 {
  81         if (!aff)
  82                 return NULL;
  83
  84         aff->ref++;
  85         return aff;
  86 }
  87
  88 __isl_give isl_aff *isl_aff_dup(__isl_keep isl_aff *aff)
  89 {
  90         if (!aff)
  91                 return NULL;
  92
  93         return isl_aff_alloc_vec(isl_local_space_copy(aff->ls),
  94                                  isl_vec_copy(aff->v));
  95 }
  96
  97 __isl_give isl_aff *isl_aff_cow(__isl_take isl_aff *aff)
  98 {
  99         if (!aff)
 100                 return NULL;
 101
 102         if (aff->ref == 1)
 103                 return aff;
 104         aff->ref--;
 105         return isl_aff_dup(aff);
 106 }
 107
 108 void *isl_aff_free(__isl_take isl_aff *aff)
 109 {
 110         if (!aff)
 111                 return NULL;
 112
 113         if (--aff->ref > 0)
 114                 return NULL;
 115
 116         isl_local_space_free(aff->ls);
 117         isl_vec_free(aff->v);
 118
 119         free(aff);
 120
 121         return NULL;
 122 }
 123
 124 isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff)
 125 {
 126         return aff ? isl_local_space_get_ctx(aff->ls) : NULL;
 127 }
 128
 129 int isl_aff_dim(__isl_keep isl_aff *aff, enum isl_dim_type type)
 130 {
 131         return aff ? isl_local_space_dim(aff->ls, type) : 0;
 132 }
 133
 134 __isl_give isl_dim *isl_aff_get_dim(__isl_keep isl_aff *aff)
 135 {
 136         return aff ? isl_local_space_get_dim(aff->ls) : NULL;
 137 }
 138
 139 __isl_give isl_local_space *isl_aff_get_local_space(__isl_keep isl_aff *aff)
 140 {
 141         return aff ? isl_local_space_copy(aff->ls) : NULL;
 142 }
 143
 144 const char *isl_aff_get_dim_name(__isl_keep isl_aff *aff,
 145         enum isl_dim_type type, unsigned pos)
 146 {
 147         return aff ? isl_local_space_get_dim_name(aff->ls, type, pos) : 0;
 148 }
 149
 150 int isl_aff_plain_is_zero(__isl_keep isl_aff *aff)
 151 {
 152         if (!aff)
 153                 return -1;
 154
 155         return isl_seq_first_non_zero(aff->v->el + 1, aff->v->size - 1) < 0;
 156 }
 157
 158 int isl_aff_plain_is_equal(__isl_keep isl_aff *aff1, __isl_keep isl_aff *aff2)
 159 {
 160         int equal;
 161
 162         if (!aff1 || !aff2)
 163                 return -1;
 164
 165         equal = isl_local_space_is_equal(aff1->ls, aff2->ls);
 166         if (equal < 0 || !equal)
 167                 return equal;
 168
 169         return isl_vec_is_equal(aff1->v, aff2->v);
 170 }
 171
 172 int isl_aff_get_denominator(__isl_keep isl_aff *aff, isl_int *v)
 173 {
 174         if (!aff)
 175                 return -1;
 176         isl_int_set(*v, aff->v->el[0]);
 177         return 0;
 178 }
 179
 180 int isl_aff_get_constant(__isl_keep isl_aff *aff, isl_int *v)
 181 {
 182         if (!aff)
 183                 return -1;
 184         isl_int_set(*v, aff->v->el[1]);
 185         return 0;
 186 }
 187
 188 int isl_aff_get_coefficient(__isl_keep isl_aff *aff,
 189         enum isl_dim_type type, int pos, isl_int *v)
 190 {
 191         if (!aff)
 192                 return -1;
 193
 194         if (pos >= isl_local_space_dim(aff->ls, type))
 195                 isl_die(aff->v->ctx, isl_error_invalid,
 196                         "position out of bounds", return -1);
 197
 198         pos += isl_local_space_offset(aff->ls, type);
 199         isl_int_set(*v, aff->v->el[1 + pos]);
 200
 201         return 0;
 202 }
 203
 204 __isl_give isl_aff *isl_aff_set_denominator(__isl_take isl_aff *aff, isl_int v)
 205 {
 206         aff = isl_aff_cow(aff);
 207         if (!aff)
 208                 return NULL;
 209
 210         aff->v = isl_vec_cow(aff->v);
 211         if (!aff->v)
 212                 return isl_aff_free(aff);
 213
 214         isl_int_set(aff->v->el[0], v);
 215
 216         return aff;
 217 }
 218
 219 __isl_give isl_aff *isl_aff_set_constant(__isl_take isl_aff *aff, isl_int v)
 220 {
 221         aff = isl_aff_cow(aff);
 222         if (!aff)
 223                 return NULL;
 224
 225         aff->v = isl_vec_cow(aff->v);
 226         if (!aff->v)
 227                 return isl_aff_free(aff);
 228
 229         isl_int_set(aff->v->el[1], v);
 230
 231         return aff;
 232 }
 233
 234 __isl_give isl_aff *isl_aff_add_constant(__isl_take isl_aff *aff, isl_int v)
 235 {
 236         if (isl_int_is_zero(v))
 237                 return aff;
 238
 239         aff = isl_aff_cow(aff);
 240         if (!aff)
 241                 return NULL;
 242
 243         aff->v = isl_vec_cow(aff->v);
 244         if (!aff->v)
 245                 return isl_aff_free(aff);
 246
 247         isl_int_addmul(aff->v->el[1], aff->v->el[0], v);
 248
 249         return aff;
 250 }
 251
 252 __isl_give isl_aff *isl_aff_add_constant_si(__isl_take isl_aff *aff, int v)
 253 {
 254         isl_int t;
 255
 256         isl_int_init(t);
 257         isl_int_set_si(t, v);
 258         aff = isl_aff_add_constant(aff, t);
 259         isl_int_clear(t);
 260
 261         return aff;
 262 }
 263
 264 __isl_give isl_aff *isl_aff_set_constant_si(__isl_take isl_aff *aff, int v)
 265 {
 266         aff = isl_aff_cow(aff);
 267         if (!aff)
 268                 return NULL;
 269
 270         aff->v = isl_vec_cow(aff->v);
 271         if (!aff->v)
 272                 return isl_aff_free(aff);
 273
 274         isl_int_set_si(aff->v->el[1], v);
 275
 276         return aff;
 277 }
 278
 279 __isl_give isl_aff *isl_aff_set_coefficient(__isl_take isl_aff *aff,
 280         enum isl_dim_type type, int pos, isl_int v)
 281 {
 282         if (!aff)
 283                 return NULL;
 284
 285         if (pos >= isl_local_space_dim(aff->ls, type))
 286                 isl_die(aff->v->ctx, isl_error_invalid,
 287                         "position out of bounds", return isl_aff_free(aff));
 288
 289         aff = isl_aff_cow(aff);
 290         if (!aff)
 291                 return NULL;
 292
 293         aff->v = isl_vec_cow(aff->v);
 294         if (!aff->v)
 295                 return isl_aff_free(aff);
 296
 297         pos += isl_local_space_offset(aff->ls, type);
 298         isl_int_set(aff->v->el[1 + pos], v);
 299
 300         return aff;
 301 }
 302
 303 __isl_give isl_aff *isl_aff_set_coefficient_si(__isl_take isl_aff *aff,
 304         enum isl_dim_type type, int pos, int v)
 305 {
 306         if (!aff)
 307                 return NULL;
 308
 309         if (pos >= isl_local_space_dim(aff->ls, type))
 310                 isl_die(aff->v->ctx, isl_error_invalid,
 311                         "position out of bounds", return isl_aff_free(aff));
 312
 313         aff = isl_aff_cow(aff);
 314         if (!aff)
 315                 return NULL;
 316
 317         aff->v = isl_vec_cow(aff->v);
 318         if (!aff->v)
 319                 return isl_aff_free(aff);
 320
 321         pos += isl_local_space_offset(aff->ls, type);
 322         isl_int_set_si(aff->v->el[1 + pos], v);
 323
 324         return aff;
 325 }
 326
 327 __isl_give isl_aff *isl_aff_add_coefficient(__isl_take isl_aff *aff,
 328         enum isl_dim_type type, int pos, isl_int v)
 329 {
 330         if (!aff)
 331                 return NULL;
 332
 333         if (pos >= isl_local_space_dim(aff->ls, type))
 334                 isl_die(aff->v->ctx, isl_error_invalid,
 335                         "position out of bounds", return isl_aff_free(aff));
 336
 337         aff = isl_aff_cow(aff);
 338         if (!aff)
 339                 return NULL;
 340
 341         aff->v = isl_vec_cow(aff->v);
 342         if (!aff->v)
 343                 return isl_aff_free(aff);
 344
 345         pos += isl_local_space_offset(aff->ls, type);
 346         isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v);
 347
 348         return aff;
 349 }
 350
 351 __isl_give isl_aff *isl_aff_add_coefficient_si(__isl_take isl_aff *aff,
 352         enum isl_dim_type type, int pos, int v)
 353 {
 354         isl_int t;
 355
 356         isl_int_init(t);
 357         isl_int_set_si(t, v);
 358         aff = isl_aff_add_coefficient(aff, type, pos, t);
 359         isl_int_clear(t);
 360
 361         return aff;
 362 }
 363
 364 __isl_give isl_div *isl_aff_get_div(__isl_keep isl_aff *aff, int pos)
 365 {
 366         if (!aff)
 367                 return NULL;
 368
 369         return isl_local_space_get_div(aff->ls, pos);
 370 }
 371
 372 __isl_give isl_aff *isl_aff_neg(__isl_take isl_aff *aff)
 373 {
 374         aff = isl_aff_cow(aff);
 375         if (!aff)
 376                 return NULL;
 377         aff->v = isl_vec_cow(aff->v);
 378         if (!aff->v)
 379                 return isl_aff_free(aff);
 380
 381         isl_seq_neg(aff->v->el + 1, aff->v->el + 1, aff->v->size - 1);
 382
 383         return aff;
 384 }
 385
 386 /* Given f, return floor(f).
 387  * If f is an integer expression, then just return f.
 388  * Otherwise, create a new div d = [f] and return the expression d.
 389  */
 390 __isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff)
 391 {
 392         int size;
 393         isl_ctx *ctx;
 394
 395         if (!aff)
 396                 return NULL;
 397
 398         if (isl_int_is_one(aff->v->el[0]))
 399                 return aff;
 400
 401         aff = isl_aff_cow(aff);
 402         if (!aff)
 403                 return NULL;
 404
 405         aff->ls = isl_local_space_add_div(aff->ls, isl_vec_copy(aff->v));
 406         if (!aff->ls)
 407                 return isl_aff_free(aff);
 408
 409         ctx = isl_aff_get_ctx(aff);
 410         size = aff->v->size;
 411         isl_vec_free(aff->v);
 412         aff->v = isl_vec_alloc(ctx, size + 1);
 413         aff->v = isl_vec_clr(aff->v);
 414         if (!aff->v)
 415                 return isl_aff_free(aff);
 416         isl_int_set_si(aff->v->el[0], 1);
 417         isl_int_set_si(aff->v->el[size], 1);
 418
 419         return aff;
 420 }
 421
 422 /* Given f, return ceil(f).
 423  * If f is an integer expression, then just return f.
 424  * Otherwise, create a new div d = [-f] and return the expression -d.
 425  */
 426 __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff)
 427 {
 428         if (!aff)
 429                 return NULL;
 430
 431         if (isl_int_is_one(aff->v->el[0]))
 432                 return aff;
 433
 434         aff = isl_aff_neg(aff);
 435         aff = isl_aff_floor(aff);
 436         aff = isl_aff_neg(aff);
 437
 438         return aff;
 439 }
 440
 441 /* Apply the expansion computed by isl_merge_divs.
 442  * The expansion itself is given by "exp" while the resulting
 443  * list of divs is given by "div".
 444  */
 445 __isl_give isl_aff *isl_aff_expand_divs( __isl_take isl_aff *aff,
 446         __isl_take isl_mat *div, int *exp)
 447 {
 448         int i, j;
 449         int old_n_div;
 450         int new_n_div;
 451         int offset;
 452
 453         aff = isl_aff_cow(aff);
 454         if (!aff || !div)
 455                 goto error;
 456
 457         old_n_div = isl_local_space_dim(aff->ls, isl_dim_div);
 458         new_n_div = isl_mat_rows(div);
 459         if (new_n_div < old_n_div)
 460                 isl_die(isl_mat_get_ctx(div), isl_error_invalid,
 461                         "not an expansion", goto error);
 462
 463         aff->v = isl_vec_extend(aff->v, aff->v->size + new_n_div - old_n_div);
 464         if (!aff->v)
 465                 goto error;
 466
 467         offset = 1 + isl_local_space_offset(aff->ls, isl_dim_div);
 468         j = old_n_div - 1;
 469         for (i = new_n_div - 1; i >= 0; --i) {
 470                 if (j >= 0 && exp[j] == i) {
 471                         if (i != j)
 472                                 isl_int_swap(aff->v->el[offset + i],
 473                                              aff->v->el[offset + j]);
 474                         j--;
 475                 } else
 476                         isl_int_set_si(aff->v->el[offset + i], 0);
 477         }
 478
 479         aff->ls = isl_local_space_replace_divs(aff->ls, isl_mat_copy(div));
 480         if (!aff->ls)
 481                 goto error;
 482         isl_mat_free(div);
 483         return aff;
 484 error:
 485         isl_aff_free(aff);
 486         isl_mat_free(div);
 487         return NULL;
 488 }
 489
 490 /* Add two affine expressions that live in the same local space.
 491  */
 492 static __isl_give isl_aff *add_expanded(__isl_take isl_aff *aff1,
 493         __isl_take isl_aff *aff2)
 494 {
 495         isl_int gcd, f;
 496
 497         aff1 = isl_aff_cow(aff1);
 498         if (!aff1 || !aff2)
 499                 goto error;
 500
 501         aff1->v = isl_vec_cow(aff1->v);
 502         if (!aff1->v)
 503                 goto error;
 504
 505         isl_int_init(gcd);
 506         isl_int_init(f);
 507         isl_int_gcd(gcd, aff1->v->el[0], aff2->v->el[0]);
 508         isl_int_divexact(f, aff2->v->el[0], gcd);
 509         isl_seq_scale(aff1->v->el + 1, aff1->v->el + 1, f, aff1->v->size - 1);
 510         isl_int_divexact(f, aff1->v->el[0], gcd);
 511         isl_seq_addmul(aff1->v->el + 1, f, aff2->v->el + 1, aff1->v->size - 1);
 512         isl_int_divexact(f, aff2->v->el[0], gcd);
 513         isl_int_mul(aff1->v->el[0], aff1->v->el[0], f);
 514         isl_int_clear(f);
 515         isl_int_clear(gcd);
 516
 517         isl_aff_free(aff2);
 518         return aff1;
 519 error:
 520         isl_aff_free(aff1);
 521         isl_aff_free(aff2);
 522         return NULL;
 523 }
 524
 525 __isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
 526         __isl_take isl_aff *aff2)
 527 {
 528         isl_ctx *ctx;
 529         int *exp1 = NULL;
 530         int *exp2 = NULL;
 531         isl_mat *div;
 532
 533         if (!aff1 || !aff2)
 534                 goto error;
 535
 536         ctx = isl_aff_get_ctx(aff1);
 537         if (!isl_dim_equal(aff1->ls->dim, aff2->ls->dim))
 538                 isl_die(ctx, isl_error_invalid,
 539                         "spaces don't match", goto error);
 540
 541         if (aff1->ls->div->n_row == 0 && aff2->ls->div->n_row == 0)
 542                 return add_expanded(aff1, aff2);
 543
 544         exp1 = isl_alloc_array(ctx, int, aff1->ls->div->n_row);
 545         exp2 = isl_alloc_array(ctx, int, aff2->ls->div->n_row);
 546         if (!exp1 || !exp2)
 547                 goto error;
 548
 549         div = isl_merge_divs(aff1->ls->div, aff2->ls->div, exp1, exp2);
 550         aff1 = isl_aff_expand_divs(aff1, isl_mat_copy(div), exp1);
 551         aff2 = isl_aff_expand_divs(aff2, div, exp2);
 552         free(exp1);
 553         free(exp2);
 554
 555         return add_expanded(aff1, aff2);
 556 error:
 557         free(exp1);
 558         free(exp2);
 559         isl_aff_free(aff1);
 560         isl_aff_free(aff2);
 561         return NULL;
 562 }
 563
 564 __isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
 565         __isl_take isl_aff *aff2)
 566 {
 567         return isl_aff_add(aff1, isl_aff_neg(aff2));
 568 }
 569
 570 __isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f)
 571 {
 572         isl_int gcd;
 573
 574         if (isl_int_is_one(f))
 575                 return aff;
 576
 577         aff = isl_aff_cow(aff);
 578         if (!aff)
 579                 return NULL;
 580         aff->v = isl_vec_cow(aff->v);
 581         if (!aff->v)
 582                 return isl_aff_free(aff);
 583
 584         isl_int_init(gcd);
 585         isl_int_gcd(gcd, aff->v->el[0], f);
 586         isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd);
 587         isl_int_divexact(gcd, f, gcd);
 588         isl_seq_scale(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
 589         isl_int_clear(gcd);
 590
 591         return aff;
 592 }
 593
 594 __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f)
 595 {
 596         isl_int gcd;
 597
 598         if (isl_int_is_one(f))
 599                 return aff;
 600
 601         aff = isl_aff_cow(aff);
 602         if (!aff)
 603                 return NULL;
 604         aff->v = isl_vec_cow(aff->v);
 605         if (!aff->v)
 606                 return isl_aff_free(aff);
 607
 608         isl_int_init(gcd);
 609         isl_seq_gcd(aff->v->el + 1, aff->v->size - 1, &gcd);
 610         isl_int_gcd(gcd, gcd, f);
 611         isl_seq_scale_down(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
 612         isl_int_divexact(gcd, f, gcd);
 613         isl_int_mul(aff->v->el[0], aff->v->el[0], gcd);
 614         isl_int_clear(gcd);
 615
 616         return aff;
 617 }
 618
 619 __isl_give isl_aff *isl_aff_scale_down_ui(__isl_take isl_aff *aff, unsigned f)
 620 {
 621         isl_int v;
 622
 623         if (f == 1)
 624                 return aff;
 625
 626         isl_int_init(v);
 627         isl_int_set_ui(v, f);
 628         aff = isl_aff_scale_down(aff, v);
 629         isl_int_clear(v);
 630
 631         return aff;
 632 }
 633
 634 __isl_give isl_aff *isl_aff_set_dim_name(__isl_take isl_aff *aff,
 635         enum isl_dim_type type, unsigned pos, const char *s)
 636 {
 637         aff = isl_aff_cow(aff);
 638         if (!aff)
 639                 return NULL;
 640         aff->ls = isl_local_space_set_dim_name(aff->ls, type, pos, s);
 641         if (!aff->ls)
 642                 return isl_aff_free(aff);
 643
 644         return aff;
 645 }
 646
 647 /* Exploit the equalities in "eq" to simplify the affine expression
 648  * and the expressions of the integer divisions in the local space.
 649  * The integer divisions in this local space are assumed to appear
 650  * as regular dimensions in "eq".
 651  */
 652 static __isl_give isl_aff *isl_aff_substitute_equalities(
 653         __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
 654 {
 655         int i, j;
 656         unsigned total;
 657         unsigned n_div;
 658
 659         if (!eq)
 660                 goto error;
 661         if (eq->n_eq == 0) {
 662                 isl_basic_set_free(eq);
 663                 return aff;
 664         }
 665
 666         aff = isl_aff_cow(aff);
 667         if (!aff)
 668                 goto error;
 669
 670         aff->ls = isl_local_space_substitute_equalities(aff->ls,
 671                                                         isl_basic_set_copy(eq));
 672         if (!aff->ls)
 673                 goto error;
 674
 675         total = 1 + isl_dim_total(eq->dim);
 676         n_div = eq->n_div;
 677         for (i = 0; i < eq->n_eq; ++i) {
 678                 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
 679                 if (j < 0 || j == 0 || j >= total)
 680                         continue;
 681
 682                 isl_seq_elim(aff->v->el + 1, eq->eq[i], j, total,
 683                                 &aff->v->el[0]);
 684         }
 685
 686         isl_basic_set_free(eq);
 687         return aff;
 688 error:
 689         isl_basic_set_free(eq);
 690         isl_aff_free(aff);
 691         return NULL;
 692 }
 693
 694 /* Look for equalities among the variables shared by context and aff
 695  * and the integer divisions of aff, if any.
 696  * The equalities are then used to eliminate coefficients and/or integer
 697  * divisions from aff.
 698  */
 699 __isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff,
 700         __isl_take isl_set *context)
 701 {
 702         isl_basic_set *hull;
 703         int n_div;
 704
 705         if (!aff)
 706                 goto error;
 707         n_div = isl_local_space_dim(aff->ls, isl_dim_div);
 708         if (n_div > 0) {
 709                 isl_basic_set *bset;
 710                 context = isl_set_add_dims(context, isl_dim_set, n_div);
 711                 bset = isl_basic_set_from_local_space(
 712                                             isl_aff_get_local_space(aff));
 713                 bset = isl_basic_set_lift(bset);
 714                 bset = isl_basic_set_flatten(bset);
 715                 context = isl_set_intersect(context,
 716                                             isl_set_from_basic_set(bset));
 717         }
 718
 719         hull = isl_set_affine_hull(context);
 720         return isl_aff_substitute_equalities(aff, hull);
 721 error:
 722         isl_aff_free(aff);
 723         isl_set_free(context);
 724         return NULL;
 725 }
 726
 727 /* Return a basic set containing those elements in the shared space
 728  * of aff1 and aff2 where aff1 is greater than or equal to aff2.
 729  */
 730 __isl_give isl_basic_set *isl_aff_ge_basic_set(__isl_take isl_aff *aff1,
 731         __isl_take isl_aff *aff2)
 732 {
 733         isl_constraint *ineq;
 734
 735         aff1 = isl_aff_sub(aff1, aff2);
 736         ineq = isl_inequality_from_aff(aff1);
 737
 738         return isl_basic_set_from_constraint(ineq);
 739 }
 740
 741 __isl_give isl_aff *isl_aff_add_on_domain(__isl_keep isl_set *dom,
 742         __isl_take isl_aff *aff1, __isl_take isl_aff *aff2)
 743 {
 744         aff1 = isl_aff_add(aff1, aff2);
 745         aff1 = isl_aff_gist(aff1, isl_set_copy(dom));
 746         return aff1;
 747 }
 748
 749 int isl_aff_is_empty(__isl_keep isl_aff *aff)
 750 {
 751         if (!aff)
 752                 return -1;
 753
 754         return 0;
 755 }
 756
 757 /* Set active[i] to 1 if the dimension at position i is involved
 758  * in the affine expression.
 759  */
 760 static int set_active(__isl_keep isl_aff *aff, int *active)
 761 {
 762         int i, j;
 763         unsigned total;
 764         unsigned offset;
 765
 766         if (!aff || !active)
 767                 return -1;
 768
 769         total = aff->v->size - 2;
 770         for (i = 0; i < total; ++i)
 771                 active[i] = !isl_int_is_zero(aff->v->el[2 + i]);
 772
 773         offset = isl_local_space_offset(aff->ls, isl_dim_div) - 1;
 774         for (i = aff->ls->div->n_row - 1; i >= 0; --i) {
 775                 if (!active[offset + i])
 776                         continue;
 777                 for (j = 0; j < total; ++j)
 778                         active[j] |=
 779                                 !isl_int_is_zero(aff->ls->div->row[i][2 + j]);
 780         }
 781
 782         return 0;
 783 }
 784
 785 /* Check whether the given affine expression has non-zero coefficient
 786  * for any dimension in the given range or if any of these dimensions
 787  * appear with non-zero coefficients in any of the integer divisions
 788  * involved in the affine expression.
 789  */
 790 int isl_aff_involves_dims(__isl_keep isl_aff *aff,
 791         enum isl_dim_type type, unsigned first, unsigned n)
 792 {
 793         int i;
 794         isl_ctx *ctx;
 795         int *active = NULL;
 796         int involves = 0;
 797
 798         if (!aff)
 799                 return -1;
 800         if (n == 0)
 801                 return 0;
 802
 803         ctx = isl_aff_get_ctx(aff);
 804         if (first + n > isl_aff_dim(aff, type))
 805                 isl_die(ctx, isl_error_invalid,
 806                         "range out of bounds", return -1);
 807
 808         active = isl_calloc_array(ctx, int,
 809                                   isl_local_space_dim(aff->ls, isl_dim_all));
 810         if (set_active(aff, active) < 0)
 811                 goto error;
 812
 813         first += isl_local_space_offset(aff->ls, type) - 1;
 814         for (i = 0; i < n; ++i)
 815                 if (active[first + i]) {
 816                         involves = 1;
 817                         break;
 818                 }
 819
 820         free(active);
 821
 822         return involves;
 823 error:
 824         free(active);
 825         return -1;
 826 }
 827
 828 __isl_give isl_aff *isl_aff_drop_dims(__isl_take isl_aff *aff,
 829         enum isl_dim_type type, unsigned first, unsigned n)
 830 {
 831         isl_ctx *ctx;
 832
 833         if (!aff)
 834                 return NULL;
 835         if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
 836                 return aff;
 837
 838         ctx = isl_aff_get_ctx(aff);
 839         if (first + n > isl_aff_dim(aff, type))
 840                 isl_die(ctx, isl_error_invalid, "range out of bounds",
 841                         return isl_aff_free(aff));
 842
 843         aff = isl_aff_cow(aff);
 844         if (!aff)
 845                 return NULL;
 846
 847         aff->ls = isl_local_space_drop_dims(aff->ls, type, first, n);
 848         if (!aff->ls)
 849                 return isl_aff_free(aff);
 850
 851         first += 1 + isl_local_space_offset(aff->ls, type);
 852         aff->v = isl_vec_drop_els(aff->v, first, n);
 853         if (!aff->v)
 854                 return isl_aff_free(aff);
 855
 856         return aff;
 857 }
 858
 859 __isl_give isl_aff *isl_aff_insert_dims(__isl_take isl_aff *aff,
 860         enum isl_dim_type type, unsigned first, unsigned n)
 861 {
 862         isl_ctx *ctx;
 863
 864         if (!aff)
 865                 return NULL;
 866         if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
 867                 return aff;
 868
 869         ctx = isl_aff_get_ctx(aff);
 870         if (first > isl_aff_dim(aff, type))
 871                 isl_die(ctx, isl_error_invalid, "position out of bounds",
 872                         return isl_aff_free(aff));
 873
 874         aff = isl_aff_cow(aff);
 875         if (!aff)
 876                 return NULL;
 877
 878         aff->ls = isl_local_space_insert_dims(aff->ls, type, first, n);
 879         if (!aff->ls)
 880                 return isl_aff_free(aff);
 881
 882         first += 1 + isl_local_space_offset(aff->ls, type);
 883         aff->v = isl_vec_insert_zero_els(aff->v, first, n);
 884         if (!aff->v)
 885                 return isl_aff_free(aff);
 886
 887         return aff;
 888 }
 889
 890 __isl_give isl_aff *isl_aff_add_dims(__isl_take isl_aff *aff,
 891         enum isl_dim_type type, unsigned n)
 892 {
 893         unsigned pos;
 894
 895         pos = isl_aff_dim(aff, type);
 896
 897         return isl_aff_insert_dims(aff, type, pos, n);
 898 }
 899
 900 __isl_give isl_pw_aff *isl_pw_aff_add_dims(__isl_take isl_pw_aff *pwaff,
 901         enum isl_dim_type type, unsigned n)
 902 {
 903         unsigned pos;
 904
 905         pos = isl_pw_aff_dim(pwaff, type);
 906
 907         return isl_pw_aff_insert_dims(pwaff, type, pos, n);
 908 }
 909
 910 #undef PW
 911 #define PW isl_pw_aff
 912 #undef EL
 913 #define EL isl_aff
 914 #undef EL_IS_ZERO
 915 #define EL_IS_ZERO is_empty
 916 #undef ZERO
 917 #define ZERO empty
 918 #undef IS_ZERO
 919 #define IS_ZERO is_empty
 920 #undef FIELD
 921 #define FIELD aff
 922
 923 #define NO_EVAL
 924 #define NO_OPT
 925 #define NO_MOVE_DIMS
 926 #define NO_REALIGN
 927 #define NO_LIFT
 928 #define NO_MORPH
 929 #define NO_RESET_DIM
 930
 931 #include <isl_pw_templ.c>
 932
 933 /* Compute a piecewise quasi-affine expression with a domain that
 934  * is the union of those of pwaff1 and pwaff2 and such that on each
 935  * cell, the quasi-affine expression is the maximum of those of pwaff1
 936  * and pwaff2.  If only one of pwaff1 or pwaff2 is defined on a given
 937  * cell, then the associated expression is the defined one.
 938  */
 939 __isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1,
 940         __isl_take isl_pw_aff *pwaff2)
 941 {
 942         int i, j, n;
 943         isl_pw_aff *res;
 944         isl_ctx *ctx;
 945         isl_set *set;
 946
 947         if (!pwaff1 || !pwaff2)
 948                 goto error;
 949
 950         ctx = isl_dim_get_ctx(pwaff1->dim);
 951         if (!isl_dim_equal(pwaff1->dim, pwaff2->dim))
 952                 isl_die(ctx, isl_error_invalid,
 953                         "arguments should live in same space", goto error);
 954
 955         if (isl_pw_aff_is_empty(pwaff1)) {
 956                 isl_pw_aff_free(pwaff1);
 957                 return pwaff2;
 958         }
 959
 960         if (isl_pw_aff_is_empty(pwaff2)) {
 961                 isl_pw_aff_free(pwaff2);
 962                 return pwaff1;
 963         }
 964
 965         n = 2 * (pwaff1->n + 1) * (pwaff2->n + 1);
 966         res = isl_pw_aff_alloc_(isl_dim_copy(pwaff1->dim), n);
 967
 968         for (i = 0; i < pwaff1->n; ++i) {
 969                 set = isl_set_copy(pwaff1->p[i].set);
 970                 for (j = 0; j < pwaff2->n; ++j) {
 971                         struct isl_set *common;
 972                         isl_set *ge;
 973
 974                         common = isl_set_intersect(
 975                                         isl_set_copy(pwaff1->p[i].set),
 976                                         isl_set_copy(pwaff2->p[j].set));
 977                         ge = isl_set_from_basic_set(isl_aff_ge_basic_set(
 978                                         isl_aff_copy(pwaff2->p[j].aff),
 979                                         isl_aff_copy(pwaff1->p[i].aff)));
 980                         ge = isl_set_intersect(common, ge);
 981                         if (isl_set_plain_is_empty(ge)) {
 982                                 isl_set_free(ge);
 983                                 continue;
 984                         }
 985                         set = isl_set_subtract(set, isl_set_copy(ge));
 986
 987                         res = isl_pw_aff_add_piece(res, ge,
 988                                                 isl_aff_copy(pwaff2->p[j].aff));
 989                 }
 990                 res = isl_pw_aff_add_piece(res, set,
 991                                                 isl_aff_copy(pwaff1->p[i].aff));
 992         }
 993
 994         for (j = 0; j < pwaff2->n; ++j) {
 995                 set = isl_set_copy(pwaff2->p[j].set);
 996                 for (i = 0; i < pwaff1->n; ++i)
 997                         set = isl_set_subtract(set,
 998                                         isl_set_copy(pwaff1->p[i].set));
 999                 res = isl_pw_aff_add_piece(res, set,
1000                                                 isl_aff_copy(pwaff2->p[j].aff));
1001         }
1002
1003         isl_pw_aff_free(pwaff1);
1004         isl_pw_aff_free(pwaff2);
1005
1006         return res;
1007 error:
1008         isl_pw_aff_free(pwaff1);
1009         isl_pw_aff_free(pwaff2);
1010         return NULL;
1011 }
1012
1013 /* Construct a map with as domain the domain of pwaff and
1014  * one-dimensional range corresponding to the affine expressions.
1015  */
1016 __isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1017 {
1018         int i;
1019         isl_dim *dim;
1020         isl_map *map;
1021
1022         if (!pwaff)
1023                 return NULL;
1024
1025         dim = isl_pw_aff_get_dim(pwaff);
1026         dim = isl_dim_from_domain(dim);
1027         dim = isl_dim_add(dim, isl_dim_out, 1);
1028         map = isl_map_empty(dim);
1029
1030         for (i = 0; i < pwaff->n; ++i) {
1031                 isl_basic_map *bmap;
1032                 isl_map *map_i;
1033
1034                 bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
1035                 map_i = isl_map_from_basic_map(bmap);
1036                 map_i = isl_map_intersect_domain(map_i,
1037                                                 isl_set_copy(pwaff->p[i].set));
1038                 map = isl_map_union_disjoint(map, map_i);
1039         }
1040
1041         isl_pw_aff_free(pwaff);
1042
1043         return map;
1044 }