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