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 space
 728  * of aff where it is non-negative.
 729  */
 730 __isl_give isl_basic_set *isl_aff_nonneg_basic_set(__isl_take isl_aff *aff)
 731 {
 732         isl_constraint *ineq;
 733
 734         ineq = isl_inequality_from_aff(aff);
 735
 736         return isl_basic_set_from_constraint(ineq);
 737 }
 738
 739 /* Return a basic set containing those elements in the shared space
 740  * of aff1 and aff2 where aff1 is greater than or equal to aff2.
 741  */
 742 __isl_give isl_basic_set *isl_aff_ge_basic_set(__isl_take isl_aff *aff1,
 743         __isl_take isl_aff *aff2)
 744 {
 745         aff1 = isl_aff_sub(aff1, aff2);
 746
 747         return isl_aff_nonneg_basic_set(aff1);
 748 }
 749
 750 __isl_give isl_aff *isl_aff_add_on_domain(__isl_keep isl_set *dom,
 751         __isl_take isl_aff *aff1, __isl_take isl_aff *aff2)
 752 {
 753         aff1 = isl_aff_add(aff1, aff2);
 754         aff1 = isl_aff_gist(aff1, isl_set_copy(dom));
 755         return aff1;
 756 }
 757
 758 int isl_aff_is_empty(__isl_keep isl_aff *aff)
 759 {
 760         if (!aff)
 761                 return -1;
 762
 763         return 0;
 764 }
 765
 766 /* Set active[i] to 1 if the dimension at position i is involved
 767  * in the affine expression.
 768  */
 769 static int set_active(__isl_keep isl_aff *aff, int *active)
 770 {
 771         int i, j;
 772         unsigned total;
 773         unsigned offset;
 774
 775         if (!aff || !active)
 776                 return -1;
 777
 778         total = aff->v->size - 2;
 779         for (i = 0; i < total; ++i)
 780                 active[i] = !isl_int_is_zero(aff->v->el[2 + i]);
 781
 782         offset = isl_local_space_offset(aff->ls, isl_dim_div) - 1;
 783         for (i = aff->ls->div->n_row - 1; i >= 0; --i) {
 784                 if (!active[offset + i])
 785                         continue;
 786                 for (j = 0; j < total; ++j)
 787                         active[j] |=
 788                                 !isl_int_is_zero(aff->ls->div->row[i][2 + j]);
 789         }
 790
 791         return 0;
 792 }
 793
 794 /* Check whether the given affine expression has non-zero coefficient
 795  * for any dimension in the given range or if any of these dimensions
 796  * appear with non-zero coefficients in any of the integer divisions
 797  * involved in the affine expression.
 798  */
 799 int isl_aff_involves_dims(__isl_keep isl_aff *aff,
 800         enum isl_dim_type type, unsigned first, unsigned n)
 801 {
 802         int i;
 803         isl_ctx *ctx;
 804         int *active = NULL;
 805         int involves = 0;
 806
 807         if (!aff)
 808                 return -1;
 809         if (n == 0)
 810                 return 0;
 811
 812         ctx = isl_aff_get_ctx(aff);
 813         if (first + n > isl_aff_dim(aff, type))
 814                 isl_die(ctx, isl_error_invalid,
 815                         "range out of bounds", return -1);
 816
 817         active = isl_calloc_array(ctx, int,
 818                                   isl_local_space_dim(aff->ls, isl_dim_all));
 819         if (set_active(aff, active) < 0)
 820                 goto error;
 821
 822         first += isl_local_space_offset(aff->ls, type) - 1;
 823         for (i = 0; i < n; ++i)
 824                 if (active[first + i]) {
 825                         involves = 1;
 826                         break;
 827                 }
 828
 829         free(active);
 830
 831         return involves;
 832 error:
 833         free(active);
 834         return -1;
 835 }
 836
 837 __isl_give isl_aff *isl_aff_drop_dims(__isl_take isl_aff *aff,
 838         enum isl_dim_type type, unsigned first, unsigned n)
 839 {
 840         isl_ctx *ctx;
 841
 842         if (!aff)
 843                 return NULL;
 844         if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
 845                 return aff;
 846
 847         ctx = isl_aff_get_ctx(aff);
 848         if (first + n > isl_aff_dim(aff, type))
 849                 isl_die(ctx, isl_error_invalid, "range out of bounds",
 850                         return isl_aff_free(aff));
 851
 852         aff = isl_aff_cow(aff);
 853         if (!aff)
 854                 return NULL;
 855
 856         aff->ls = isl_local_space_drop_dims(aff->ls, type, first, n);
 857         if (!aff->ls)
 858                 return isl_aff_free(aff);
 859
 860         first += 1 + isl_local_space_offset(aff->ls, type);
 861         aff->v = isl_vec_drop_els(aff->v, first, n);
 862         if (!aff->v)
 863                 return isl_aff_free(aff);
 864
 865         return aff;
 866 }
 867
 868 __isl_give isl_aff *isl_aff_insert_dims(__isl_take isl_aff *aff,
 869         enum isl_dim_type type, unsigned first, unsigned n)
 870 {
 871         isl_ctx *ctx;
 872
 873         if (!aff)
 874                 return NULL;
 875         if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
 876                 return aff;
 877
 878         ctx = isl_aff_get_ctx(aff);
 879         if (first > isl_aff_dim(aff, type))
 880                 isl_die(ctx, isl_error_invalid, "position out of bounds",
 881                         return isl_aff_free(aff));
 882
 883         aff = isl_aff_cow(aff);
 884         if (!aff)
 885                 return NULL;
 886
 887         aff->ls = isl_local_space_insert_dims(aff->ls, type, first, n);
 888         if (!aff->ls)
 889                 return isl_aff_free(aff);
 890
 891         first += 1 + isl_local_space_offset(aff->ls, type);
 892         aff->v = isl_vec_insert_zero_els(aff->v, first, n);
 893         if (!aff->v)
 894                 return isl_aff_free(aff);
 895
 896         return aff;
 897 }
 898
 899 __isl_give isl_aff *isl_aff_add_dims(__isl_take isl_aff *aff,
 900         enum isl_dim_type type, unsigned n)
 901 {
 902         unsigned pos;
 903
 904         pos = isl_aff_dim(aff, type);
 905
 906         return isl_aff_insert_dims(aff, type, pos, n);
 907 }
 908
 909 __isl_give isl_pw_aff *isl_pw_aff_add_dims(__isl_take isl_pw_aff *pwaff,
 910         enum isl_dim_type type, unsigned n)
 911 {
 912         unsigned pos;
 913
 914         pos = isl_pw_aff_dim(pwaff, type);
 915
 916         return isl_pw_aff_insert_dims(pwaff, type, pos, n);
 917 }
 918
 919 #undef PW
 920 #define PW isl_pw_aff
 921 #undef EL
 922 #define EL isl_aff
 923 #undef EL_IS_ZERO
 924 #define EL_IS_ZERO is_empty
 925 #undef ZERO
 926 #define ZERO empty
 927 #undef IS_ZERO
 928 #define IS_ZERO is_empty
 929 #undef FIELD
 930 #define FIELD aff
 931
 932 #define NO_EVAL
 933 #define NO_OPT
 934 #define NO_MOVE_DIMS
 935 #define NO_REALIGN
 936 #define NO_LIFT
 937 #define NO_MORPH
 938 #define NO_RESET_DIM
 939
 940 #include <isl_pw_templ.c>
 941
 942 /* Compute a piecewise quasi-affine expression with a domain that
 943  * is the union of those of pwaff1 and pwaff2 and such that on each
 944  * cell, the quasi-affine expression is the maximum of those of pwaff1
 945  * and pwaff2.  If only one of pwaff1 or pwaff2 is defined on a given
 946  * cell, then the associated expression is the defined one.
 947  */
 948 __isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1,
 949         __isl_take isl_pw_aff *pwaff2)
 950 {
 951         int i, j, n;
 952         isl_pw_aff *res;
 953         isl_ctx *ctx;
 954         isl_set *set;
 955
 956         if (!pwaff1 || !pwaff2)
 957                 goto error;
 958
 959         ctx = isl_dim_get_ctx(pwaff1->dim);
 960         if (!isl_dim_equal(pwaff1->dim, pwaff2->dim))
 961                 isl_die(ctx, isl_error_invalid,
 962                         "arguments should live in same space", goto error);
 963
 964         if (isl_pw_aff_is_empty(pwaff1)) {
 965                 isl_pw_aff_free(pwaff1);
 966                 return pwaff2;
 967         }
 968
 969         if (isl_pw_aff_is_empty(pwaff2)) {
 970                 isl_pw_aff_free(pwaff2);
 971                 return pwaff1;
 972         }
 973
 974         n = 2 * (pwaff1->n + 1) * (pwaff2->n + 1);
 975         res = isl_pw_aff_alloc_(isl_dim_copy(pwaff1->dim), n);
 976
 977         for (i = 0; i < pwaff1->n; ++i) {
 978                 set = isl_set_copy(pwaff1->p[i].set);
 979                 for (j = 0; j < pwaff2->n; ++j) {
 980                         struct isl_set *common;
 981                         isl_set *ge;
 982
 983                         common = isl_set_intersect(
 984                                         isl_set_copy(pwaff1->p[i].set),
 985                                         isl_set_copy(pwaff2->p[j].set));
 986                         ge = isl_set_from_basic_set(isl_aff_ge_basic_set(
 987                                         isl_aff_copy(pwaff2->p[j].aff),
 988                                         isl_aff_copy(pwaff1->p[i].aff)));
 989                         ge = isl_set_intersect(common, ge);
 990                         if (isl_set_plain_is_empty(ge)) {
 991                                 isl_set_free(ge);
 992                                 continue;
 993                         }
 994                         set = isl_set_subtract(set, isl_set_copy(ge));
 995
 996                         res = isl_pw_aff_add_piece(res, ge,
 997                                                 isl_aff_copy(pwaff2->p[j].aff));
 998                 }
 999                 res = isl_pw_aff_add_piece(res, set,
1000                                                 isl_aff_copy(pwaff1->p[i].aff));
1001         }
1002
1003         for (j = 0; j < pwaff2->n; ++j) {
1004                 set = isl_set_copy(pwaff2->p[j].set);
1005                 for (i = 0; i < pwaff1->n; ++i)
1006                         set = isl_set_subtract(set,
1007                                         isl_set_copy(pwaff1->p[i].set));
1008                 res = isl_pw_aff_add_piece(res, set,
1009                                                 isl_aff_copy(pwaff2->p[j].aff));
1010         }
1011
1012         isl_pw_aff_free(pwaff1);
1013         isl_pw_aff_free(pwaff2);
1014
1015         return res;
1016 error:
1017         isl_pw_aff_free(pwaff1);
1018         isl_pw_aff_free(pwaff2);
1019         return NULL;
1020 }
1021
1022 /* Construct a map with as domain the domain of pwaff and
1023  * one-dimensional range corresponding to the affine expressions.
1024  */
1025 __isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1026 {
1027         int i;
1028         isl_dim *dim;
1029         isl_map *map;
1030
1031         if (!pwaff)
1032                 return NULL;
1033
1034         dim = isl_pw_aff_get_dim(pwaff);
1035         dim = isl_dim_from_domain(dim);
1036         dim = isl_dim_add(dim, isl_dim_out, 1);
1037         map = isl_map_empty(dim);
1038
1039         for (i = 0; i < pwaff->n; ++i) {
1040                 isl_basic_map *bmap;
1041                 isl_map *map_i;
1042
1043                 bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
1044                 map_i = isl_map_from_basic_map(bmap);
1045                 map_i = isl_map_intersect_domain(map_i,
1046                                                 isl_set_copy(pwaff->p[i].set));
1047                 map = isl_map_union_disjoint(map, map_i);
1048         }
1049
1050         isl_pw_aff_free(pwaff);
1051
1052         return map;
1053 }
1054
1055 /* Return a set containing those elements in the domain
1056  * of pwaff where it is non-negative.
1057  */
1058 __isl_give isl_set *isl_pw_aff_nonneg_set(__isl_take isl_pw_aff *pwaff)
1059 {
1060         int i;
1061         isl_set *set;
1062
1063         if (!pwaff)
1064                 return NULL;
1065
1066         set = isl_set_empty(isl_pw_aff_get_dim(pwaff));
1067
1068         for (i = 0; i < pwaff->n; ++i) {
1069                 isl_basic_set *bset;
1070                 isl_set *set_i;
1071
1072                 bset = isl_aff_nonneg_basic_set(isl_aff_copy(pwaff->p[i].aff));
1073                 set_i = isl_set_from_basic_set(bset);
1074                 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1075                 set = isl_set_union_disjoint(set, set_i);
1076         }
1077
1078         isl_pw_aff_free(pwaff);
1079
1080         return set;
1081 }
1082
1083 /* Return a set containing those elements in the shared domain
1084  * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
1085  */
1086 __isl_give isl_set *isl_pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1087         __isl_take isl_pw_aff *pwaff2)
1088 {
1089         isl_set *set1, *set2;
1090
1091         set1 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff1));
1092         set2 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff2));
1093         set1 = isl_set_intersect(set1, set2);
1094         pwaff1 = isl_pw_aff_intersect_domain(pwaff1, isl_set_copy(set1));
1095         pwaff2 = isl_pw_aff_intersect_domain(pwaff2, set1);
1096         pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_neg(pwaff2));
1097
1098         return isl_pw_aff_nonneg_set(pwaff1);
1099 }