isl_local_space.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_ctx_private.h>
  12 #include <isl_map_private.h>
  13 #include <isl_local_space_private.h>
  14 #include <isl_space_private.h>
  15 #include <isl_mat_private.h>
  16 #include <isl_aff_private.h>
  17 #include <isl/seq.h>
  18
  19 isl_ctx *isl_local_space_get_ctx(__isl_keep isl_local_space *ls)
  20 {
  21         return ls ? ls->dim->ctx : NULL;
  22 }
  23
  24 __isl_give isl_local_space *isl_local_space_alloc_div(__isl_take isl_space *dim,
  25         __isl_take isl_mat *div)
  26 {
  27         isl_ctx *ctx;
  28         isl_local_space *ls = NULL;
  29
  30         if (!dim)
  31                 goto error;
  32
  33         ctx = isl_space_get_ctx(dim);
  34         ls = isl_calloc_type(ctx, struct isl_local_space);
  35         if (!ls)
  36                 goto error;
  37
  38         ls->ref = 1;
  39         ls->dim = dim;
  40         ls->div = div;
  41
  42         return ls;
  43 error:
  44         isl_space_free(dim);
  45         isl_local_space_free(ls);
  46         return NULL;
  47 }
  48
  49 __isl_give isl_local_space *isl_local_space_alloc(__isl_take isl_space *dim,
  50         unsigned n_div)
  51 {
  52         isl_ctx *ctx;
  53         isl_mat *div;
  54         unsigned total;
  55
  56         if (!dim)
  57                 return NULL;
  58
  59         total = isl_space_dim(dim, isl_dim_all);
  60
  61         ctx = isl_space_get_ctx(dim);
  62         div = isl_mat_alloc(ctx, n_div, 1 + 1 + total + n_div);
  63         return isl_local_space_alloc_div(dim, div);
  64 }
  65
  66 __isl_give isl_local_space *isl_local_space_from_space(__isl_take isl_space *dim)
  67 {
  68         return isl_local_space_alloc(dim, 0);
  69 }
  70
  71 __isl_give isl_local_space *isl_local_space_copy(__isl_keep isl_local_space *ls)
  72 {
  73         if (!ls)
  74                 return NULL;
  75
  76         ls->ref++;
  77         return ls;
  78 }
  79
  80 __isl_give isl_local_space *isl_local_space_dup(__isl_keep isl_local_space *ls)
  81 {
  82         if (!ls)
  83                 return NULL;
  84
  85         return isl_local_space_alloc_div(isl_space_copy(ls->dim),
  86                                          isl_mat_copy(ls->div));
  87
  88 }
  89
  90 __isl_give isl_local_space *isl_local_space_cow(__isl_take isl_local_space *ls)
  91 {
  92         if (!ls)
  93                 return NULL;
  94
  95         if (ls->ref == 1)
  96                 return ls;
  97         ls->ref--;
  98         return isl_local_space_dup(ls);
  99 }
 100
 101 void *isl_local_space_free(__isl_take isl_local_space *ls)
 102 {
 103         if (!ls)
 104                 return NULL;
 105
 106         if (--ls->ref > 0)
 107                 return NULL;
 108
 109         isl_space_free(ls->dim);
 110         isl_mat_free(ls->div);
 111
 112         free(ls);
 113
 114         return NULL;
 115 }
 116
 117 /* Is the local space that of a set?
 118  */
 119 int isl_local_space_is_set(__isl_keep isl_local_space *ls)
 120 {
 121         return ls ? isl_space_is_set(ls->dim) : -1;
 122 }
 123
 124 /* Return true if the two local spaces are identical, with identical
 125  * expressions for the integer divisions.
 126  */
 127 int isl_local_space_is_equal(__isl_keep isl_local_space *ls1,
 128         __isl_keep isl_local_space *ls2)
 129 {
 130         int equal;
 131
 132         if (!ls1 || !ls2)
 133                 return -1;
 134
 135         equal = isl_space_is_equal(ls1->dim, ls2->dim);
 136         if (equal < 0 || !equal)
 137                 return equal;
 138
 139         if (!isl_local_space_divs_known(ls1))
 140                 return 0;
 141         if (!isl_local_space_divs_known(ls2))
 142                 return 0;
 143
 144         return isl_mat_is_equal(ls1->div, ls2->div);
 145 }
 146
 147 int isl_local_space_dim(__isl_keep isl_local_space *ls,
 148         enum isl_dim_type type)
 149 {
 150         if (!ls)
 151                 return 0;
 152         if (type == isl_dim_div)
 153                 return ls->div->n_row;
 154         if (type == isl_dim_all)
 155                 return isl_space_dim(ls->dim, isl_dim_all) + ls->div->n_row;
 156         return isl_space_dim(ls->dim, type);
 157 }
 158
 159 unsigned isl_local_space_offset(__isl_keep isl_local_space *ls,
 160         enum isl_dim_type type)
 161 {
 162         isl_space *dim;
 163
 164         if (!ls)
 165                 return 0;
 166
 167         dim = ls->dim;
 168         switch (type) {
 169         case isl_dim_cst:       return 0;
 170         case isl_dim_param:     return 1;
 171         case isl_dim_in:        return 1 + dim->nparam;
 172         case isl_dim_out:       return 1 + dim->nparam + dim->n_in;
 173         case isl_dim_div:       return 1 + dim->nparam + dim->n_in + dim->n_out;
 174         default:                return 0;
 175         }
 176 }
 177
 178 const char *isl_local_space_get_dim_name(__isl_keep isl_local_space *ls,
 179         enum isl_dim_type type, unsigned pos)
 180 {
 181         return ls ? isl_space_get_dim_name(ls->dim, type, pos) : NULL;
 182 }
 183
 184 __isl_give isl_aff *isl_local_space_get_div(__isl_keep isl_local_space *ls,
 185         int pos)
 186 {
 187         isl_aff *aff;
 188
 189         if (!ls)
 190                 return NULL;
 191
 192         if (pos < 0 || pos >= ls->div->n_row)
 193                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 194                         "index out of bounds", return NULL);
 195
 196         if (isl_int_is_zero(ls->div->row[pos][0]))
 197                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 198                         "expression of div unknown", return NULL);
 199
 200         aff = isl_aff_alloc(isl_local_space_copy(ls));
 201         if (!aff)
 202                 return NULL;
 203         isl_seq_cpy(aff->v->el, ls->div->row[pos], aff->v->size);
 204         return aff;
 205 }
 206
 207 __isl_give isl_space *isl_local_space_get_space(__isl_keep isl_local_space *ls)
 208 {
 209         if (!ls)
 210                 return NULL;
 211
 212         return isl_space_copy(ls->dim);
 213 }
 214
 215 __isl_give isl_local_space *isl_local_space_set_dim_name(
 216         __isl_take isl_local_space *ls,
 217         enum isl_dim_type type, unsigned pos, const char *s)
 218 {
 219         ls = isl_local_space_cow(ls);
 220         if (!ls)
 221                 return NULL;
 222         ls->dim = isl_space_set_dim_name(ls->dim, type, pos, s);
 223         if (!ls->dim)
 224                 return isl_local_space_free(ls);
 225
 226         return ls;
 227 }
 228
 229 __isl_give isl_local_space *isl_local_space_set_dim_id(
 230         __isl_take isl_local_space *ls,
 231         enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
 232 {
 233         ls = isl_local_space_cow(ls);
 234         if (!ls)
 235                 return isl_id_free(id);
 236         ls->dim = isl_space_set_dim_id(ls->dim, type, pos, id);
 237         if (!ls->dim)
 238                 return isl_local_space_free(ls);
 239
 240         return ls;
 241 }
 242
 243 __isl_give isl_local_space *isl_local_space_reset_space(
 244         __isl_take isl_local_space *ls, __isl_take isl_space *dim)
 245 {
 246         ls = isl_local_space_cow(ls);
 247         if (!ls || !dim)
 248                 goto error;
 249
 250         isl_space_free(ls->dim);
 251         ls->dim = dim;
 252
 253         return ls;
 254 error:
 255         isl_local_space_free(ls);
 256         isl_space_free(dim);
 257         return NULL;
 258 }
 259
 260 /* Reorder the columns of the given div definitions according to the
 261  * given reordering.
 262  * The order of the divs themselves is assumed not to change.
 263  */
 264 static __isl_give isl_mat *reorder_divs(__isl_take isl_mat *div,
 265         __isl_take isl_reordering *r)
 266 {
 267         int i, j;
 268         isl_mat *mat;
 269         int extra;
 270
 271         if (!div || !r)
 272                 goto error;
 273
 274         extra = isl_space_dim(r->dim, isl_dim_all) + div->n_row - r->len;
 275         mat = isl_mat_alloc(div->ctx, div->n_row, div->n_col + extra);
 276         if (!mat)
 277                 goto error;
 278
 279         for (i = 0; i < div->n_row; ++i) {
 280                 isl_seq_cpy(mat->row[i], div->row[i], 2);
 281                 isl_seq_clr(mat->row[i] + 2, mat->n_col - 2);
 282                 for (j = 0; j < r->len; ++j)
 283                         isl_int_set(mat->row[i][2 + r->pos[j]],
 284                                     div->row[i][2 + j]);
 285         }
 286
 287         isl_reordering_free(r);
 288         isl_mat_free(div);
 289         return mat;
 290 error:
 291         isl_reordering_free(r);
 292         isl_mat_free(div);
 293         return NULL;
 294 }
 295
 296 /* Reorder the dimensions of "ls" according to the given reordering.
 297  * The reordering r is assumed to have been extended with the local
 298  * variables, leaving them in the same order.
 299  */
 300 __isl_give isl_local_space *isl_local_space_realign(
 301         __isl_take isl_local_space *ls, __isl_take isl_reordering *r)
 302 {
 303         ls = isl_local_space_cow(ls);
 304         if (!ls || !r)
 305                 goto error;
 306
 307         ls->div = reorder_divs(ls->div, isl_reordering_copy(r));
 308         if (!ls->div)
 309                 goto error;
 310
 311         ls = isl_local_space_reset_space(ls, isl_space_copy(r->dim));
 312
 313         isl_reordering_free(r);
 314         return ls;
 315 error:
 316         isl_local_space_free(ls);
 317         isl_reordering_free(r);
 318         return NULL;
 319 }
 320
 321 __isl_give isl_local_space *isl_local_space_add_div(
 322         __isl_take isl_local_space *ls, __isl_take isl_vec *div)
 323 {
 324         ls = isl_local_space_cow(ls);
 325         if (!ls || !div)
 326                 goto error;
 327
 328         if (ls->div->n_col != div->size)
 329                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 330                         "incompatible dimensions", goto error);
 331
 332         ls->div = isl_mat_add_zero_cols(ls->div, 1);
 333         ls->div = isl_mat_add_rows(ls->div, 1);
 334         if (!ls->div)
 335                 goto error;
 336
 337         isl_seq_cpy(ls->div->row[ls->div->n_row - 1], div->el, div->size);
 338         isl_int_set_si(ls->div->row[ls->div->n_row - 1][div->size], 0);
 339
 340         isl_vec_free(div);
 341         return ls;
 342 error:
 343         isl_local_space_free(ls);
 344         isl_vec_free(div);
 345         return NULL;
 346 }
 347
 348 __isl_give isl_local_space *isl_local_space_replace_divs(
 349         __isl_take isl_local_space *ls, __isl_take isl_mat *div)
 350 {
 351         ls = isl_local_space_cow(ls);
 352
 353         if (!ls || !div)
 354                 goto error;
 355
 356         isl_mat_free(ls->div);
 357         ls->div = div;
 358         return ls;
 359 error:
 360         isl_mat_free(div);
 361         isl_local_space_free(ls);
 362         return NULL;
 363 }
 364
 365 /* Copy row "s" of "src" to row "d" of "dst", applying the expansion
 366  * defined by "exp".
 367  */
 368 static void expand_row(__isl_keep isl_mat *dst, int d,
 369         __isl_keep isl_mat *src, int s, int *exp)
 370 {
 371         int i;
 372         unsigned c = src->n_col - src->n_row;
 373
 374         isl_seq_cpy(dst->row[d], src->row[s], c);
 375         isl_seq_clr(dst->row[d] + c, dst->n_col - c);
 376
 377         for (i = 0; i < s; ++i)
 378                 isl_int_set(dst->row[d][c + exp[i]], src->row[s][c + i]);
 379 }
 380
 381 /* Compare (known) divs.
 382  * Return non-zero if at least one of the two divs is unknown.
 383  */
 384 static int cmp_row(__isl_keep isl_mat *div, int i, int j)
 385 {
 386         int li, lj;
 387
 388         if (isl_int_is_zero(div->row[j][0]))
 389                 return -1;
 390         if (isl_int_is_zero(div->row[i][0]))
 391                 return 1;
 392
 393         li = isl_seq_last_non_zero(div->row[i], div->n_col);
 394         lj = isl_seq_last_non_zero(div->row[j], div->n_col);
 395
 396         if (li != lj)
 397                 return li - lj;
 398
 399         return isl_seq_cmp(div->row[i], div->row[j], div->n_col);
 400 }
 401
 402 /* Combine the two lists of divs into a single list.
 403  * For each row i in div1, exp1[i] is set to the position of the corresponding
 404  * row in the result.  Similarly for div2 and exp2.
 405  * This function guarantees
 406  *      exp1[i] >= i
 407  *      exp1[i+1] > exp1[i]
 408  * For optimal merging, the two input list should have been sorted.
 409  */
 410 __isl_give isl_mat *isl_merge_divs(__isl_keep isl_mat *div1,
 411         __isl_keep isl_mat *div2, int *exp1, int *exp2)
 412 {
 413         int i, j, k;
 414         isl_mat *div = NULL;
 415         unsigned d = div1->n_col - div1->n_row;
 416
 417         div = isl_mat_alloc(div1->ctx, 1 + div1->n_row + div2->n_row,
 418                                 d + div1->n_row + div2->n_row);
 419         if (!div)
 420                 return NULL;
 421
 422         for (i = 0, j = 0, k = 0; i < div1->n_row && j < div2->n_row; ++k) {
 423                 int cmp;
 424
 425                 expand_row(div, k, div1, i, exp1);
 426                 expand_row(div, k + 1, div2, j, exp2);
 427
 428                 cmp = cmp_row(div, k, k + 1);
 429                 if (cmp == 0) {
 430                         exp1[i++] = k;
 431                         exp2[j++] = k;
 432                 } else if (cmp < 0) {
 433                         exp1[i++] = k;
 434                 } else {
 435                         exp2[j++] = k;
 436                         isl_seq_cpy(div->row[k], div->row[k + 1], div->n_col);
 437                 }
 438         }
 439         for (; i < div1->n_row; ++i, ++k) {
 440                 expand_row(div, k, div1, i, exp1);
 441                 exp1[i] = k;
 442         }
 443         for (; j < div2->n_row; ++j, ++k) {
 444                 expand_row(div, k, div2, j, exp2);
 445                 exp2[j] = k;
 446         }
 447
 448         div->n_row = k;
 449         div->n_col = d + k;
 450
 451         return div;
 452 }
 453
 454 int isl_local_space_divs_known(__isl_keep isl_local_space *ls)
 455 {
 456         int i;
 457
 458         if (!ls)
 459                 return -1;
 460
 461         for (i = 0; i < ls->div->n_row; ++i)
 462                 if (isl_int_is_zero(ls->div->row[i][0]))
 463                         return 0;
 464
 465         return 1;
 466 }
 467
 468 __isl_give isl_local_space *isl_local_space_domain(
 469         __isl_take isl_local_space *ls)
 470 {
 471         ls = isl_local_space_drop_dims(ls, isl_dim_out,
 472                                         0, isl_local_space_dim(ls, isl_dim_out));
 473         ls = isl_local_space_cow(ls);
 474         if (!ls)
 475                 return NULL;
 476         ls->dim = isl_space_domain(ls->dim);
 477         if (!ls->dim)
 478                 return isl_local_space_free(ls);
 479         return ls;
 480 }
 481
 482 /* Construct a local space for a map that has the given local
 483  * space as domain and that has a zero-dimensional range.
 484  */
 485 __isl_give isl_local_space *isl_local_space_from_domain(
 486         __isl_take isl_local_space *ls)
 487 {
 488         ls = isl_local_space_cow(ls);
 489         if (!ls)
 490                 return NULL;
 491         ls->dim = isl_space_from_domain(ls->dim);
 492         if (!ls->dim)
 493                 return isl_local_space_free(ls);
 494         return ls;
 495 }
 496
 497 __isl_give isl_local_space *isl_local_space_add_dims(
 498         __isl_take isl_local_space *ls, enum isl_dim_type type, unsigned n)
 499 {
 500         int pos;
 501
 502         if (!ls)
 503                 return NULL;
 504         pos = isl_local_space_dim(ls, type);
 505         return isl_local_space_insert_dims(ls, type, pos, n);
 506 }
 507
 508 /* Remove common factor of non-constant terms and denominator.
 509  */
 510 static void normalize_div(__isl_keep isl_local_space *ls, int div)
 511 {
 512         isl_ctx *ctx = ls->div->ctx;
 513         unsigned total = ls->div->n_col - 2;
 514
 515         isl_seq_gcd(ls->div->row[div] + 2, total, &ctx->normalize_gcd);
 516         isl_int_gcd(ctx->normalize_gcd,
 517                     ctx->normalize_gcd, ls->div->row[div][0]);
 518         if (isl_int_is_one(ctx->normalize_gcd))
 519                 return;
 520
 521         isl_seq_scale_down(ls->div->row[div] + 2, ls->div->row[div] + 2,
 522                             ctx->normalize_gcd, total);
 523         isl_int_divexact(ls->div->row[div][0], ls->div->row[div][0],
 524                             ctx->normalize_gcd);
 525         isl_int_fdiv_q(ls->div->row[div][1], ls->div->row[div][1],
 526                             ctx->normalize_gcd);
 527 }
 528
 529 /* Exploit the equalities in "eq" to simplify the expressions of
 530  * the integer divisions in "ls".
 531  * The integer divisions in "ls" are assumed to appear as regular
 532  * dimensions in "eq".
 533  */
 534 __isl_give isl_local_space *isl_local_space_substitute_equalities(
 535         __isl_take isl_local_space *ls, __isl_take isl_basic_set *eq)
 536 {
 537         int i, j, k;
 538         unsigned total;
 539         unsigned n_div;
 540
 541         ls = isl_local_space_cow(ls);
 542         if (!ls || !eq)
 543                 goto error;
 544
 545         total = isl_space_dim(eq->dim, isl_dim_all);
 546         if (isl_local_space_dim(ls, isl_dim_all) != total)
 547                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 548                         "dimensions don't match", goto error);
 549         total++;
 550         n_div = eq->n_div;
 551         for (i = 0; i < eq->n_eq; ++i) {
 552                 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
 553                 if (j < 0 || j == 0 || j >= total)
 554                         continue;
 555
 556                 for (k = 0; k < ls->div->n_row; ++k) {
 557                         if (isl_int_is_zero(ls->div->row[k][1 + j]))
 558                                 continue;
 559                         isl_seq_elim(ls->div->row[k] + 1, eq->eq[i], j, total,
 560                                         &ls->div->row[k][0]);
 561                         normalize_div(ls, k);
 562                 }
 563         }
 564
 565         isl_basic_set_free(eq);
 566         return ls;
 567 error:
 568         isl_basic_set_free(eq);
 569         isl_local_space_free(ls);
 570         return NULL;
 571 }
 572
 573 /* Plug in "subs" for dimension "type", "pos" in the integer divisions
 574  * of "ls".
 575  *
 576  * Let i be the dimension to replace and let "subs" be of the form
 577  *
 578  *      f/d
 579  *
 580  * Any integer division with a non-zero coefficient for i,
 581  *
 582  *      floor((a i + g)/m)
 583  *
 584  * is replaced by
 585  *
 586  *      floor((a f + d g)/(m d))
 587  */
 588 __isl_give isl_local_space *isl_local_space_substitute(
 589         __isl_take isl_local_space *ls,
 590         enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs)
 591 {
 592         int i;
 593         isl_int v;
 594
 595         ls = isl_local_space_cow(ls);
 596         if (!ls || !subs)
 597                 return isl_local_space_free(ls);
 598
 599         if (!isl_space_is_equal(ls->dim, subs->ls->dim))
 600                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
 601                         "spaces don't match", return isl_local_space_free(ls));
 602         if (isl_local_space_dim(subs->ls, isl_dim_div) != 0)
 603                 isl_die(isl_local_space_get_ctx(ls), isl_error_unsupported,
 604                         "cannot handle divs yet",
 605                         return isl_local_space_free(ls));
 606
 607         pos += isl_local_space_offset(ls, type);
 608
 609         isl_int_init(v);
 610         for (i = 0; i < ls->div->n_row; ++i) {
 611                 if (isl_int_is_zero(ls->div->row[i][1 + pos]))
 612                         continue;
 613                 isl_int_set(v, ls->div->row[i][1 + pos]);
 614                 isl_int_set_si(ls->div->row[i][1 + pos], 0);
 615                 isl_seq_combine(ls->div->row[i] + 1,
 616                                 subs->v->el[0], ls->div->row[i] + 1,
 617                                 v, subs->v->el + 1, subs->v->size - 1);
 618                 isl_int_mul(ls->div->row[i][0],
 619                             ls->div->row[i][0], subs->v->el[0]);
 620                 normalize_div(ls, i);
 621         }
 622         isl_int_clear(v);
 623
 624         return ls;
 625 }
 626
 627 int isl_local_space_is_named_or_nested(__isl_keep isl_local_space *ls,
 628         enum isl_dim_type type)
 629 {
 630         if (!ls)
 631                 return -1;
 632         return isl_space_is_named_or_nested(ls->dim, type);
 633 }
 634
 635 __isl_give isl_local_space *isl_local_space_drop_dims(
 636         __isl_take isl_local_space *ls,
 637         enum isl_dim_type type, unsigned first, unsigned n)
 638 {
 639         isl_ctx *ctx;
 640
 641         if (!ls)
 642                 return NULL;
 643         if (n == 0 && !isl_local_space_is_named_or_nested(ls, type))
 644                 return ls;
 645
 646         ctx = isl_local_space_get_ctx(ls);
 647         if (first + n > isl_local_space_dim(ls, type))
 648                 isl_die(ctx, isl_error_invalid, "range out of bounds",
 649                         return isl_local_space_free(ls));
 650
 651         ls = isl_local_space_cow(ls);
 652         if (!ls)
 653                 return NULL;
 654
 655         if (type == isl_dim_div) {
 656                 ls->div = isl_mat_drop_rows(ls->div, first, n);
 657         } else {
 658                 ls->dim = isl_space_drop_dims(ls->dim, type, first, n);
 659                 if (!ls->dim)
 660                         return isl_local_space_free(ls);
 661         }
 662
 663         first += 1 + isl_local_space_offset(ls, type);
 664         ls->div = isl_mat_drop_cols(ls->div, first, n);
 665         if (!ls->div)
 666                 return isl_local_space_free(ls);
 667
 668         return ls;
 669 }
 670
 671 __isl_give isl_local_space *isl_local_space_insert_dims(
 672         __isl_take isl_local_space *ls,
 673         enum isl_dim_type type, unsigned first, unsigned n)
 674 {
 675         isl_ctx *ctx;
 676
 677         if (!ls)
 678                 return NULL;
 679         if (n == 0 && !isl_local_space_is_named_or_nested(ls, type))
 680                 return ls;
 681
 682         ctx = isl_local_space_get_ctx(ls);
 683         if (first > isl_local_space_dim(ls, type))
 684                 isl_die(ctx, isl_error_invalid, "position out of bounds",
 685                         return isl_local_space_free(ls));
 686
 687         ls = isl_local_space_cow(ls);
 688         if (!ls)
 689                 return NULL;
 690
 691         if (type == isl_dim_div) {
 692                 ls->div = isl_mat_insert_zero_rows(ls->div, first, n);
 693         } else {
 694                 ls->dim = isl_space_insert_dims(ls->dim, type, first, n);
 695                 if (!ls->dim)
 696                         return isl_local_space_free(ls);
 697         }
 698
 699         first += 1 + isl_local_space_offset(ls, type);
 700         ls->div = isl_mat_insert_zero_cols(ls->div, first, n);
 701         if (!ls->div)
 702                 return isl_local_space_free(ls);
 703
 704         return ls;
 705 }
 706
 707 /* Check if the constraints pointed to by "constraint" is a div
 708  * constraint corresponding to div "div" in "ls".
 709  *
 710  * That is, if div = floor(f/m), then check if the constraint is
 711  *
 712  *              f - m d >= 0
 713  * or
 714  *              -(f-(m-1)) + m d >= 0
 715  */
 716 int isl_local_space_is_div_constraint(__isl_keep isl_local_space *ls,
 717         isl_int *constraint, unsigned div)
 718 {
 719         unsigned pos;
 720
 721         if (!ls)
 722                 return -1;
 723
 724         if (isl_int_is_zero(ls->div->row[div][0]))
 725                 return 0;
 726
 727         pos = isl_local_space_offset(ls, isl_dim_div) + div;
 728
 729         if (isl_int_eq(constraint[pos], ls->div->row[div][0])) {
 730                 int neg;
 731                 isl_int_sub(ls->div->row[div][1],
 732                                 ls->div->row[div][1], ls->div->row[div][0]);
 733                 isl_int_add_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
 734                 neg = isl_seq_is_neg(constraint, ls->div->row[div]+1, pos);
 735                 isl_int_sub_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
 736                 isl_int_add(ls->div->row[div][1],
 737                                 ls->div->row[div][1], ls->div->row[div][0]);
 738                 if (!neg)
 739                         return 0;
 740                 if (isl_seq_first_non_zero(constraint+pos+1,
 741                                             ls->div->n_row-div-1) != -1)
 742                         return 0;
 743         } else if (isl_int_abs_eq(constraint[pos], ls->div->row[div][0])) {
 744                 if (!isl_seq_eq(constraint, ls->div->row[div]+1, pos))
 745                         return 0;
 746                 if (isl_seq_first_non_zero(constraint+pos+1,
 747                                             ls->div->n_row-div-1) != -1)
 748                         return 0;
 749         } else
 750                 return 0;
 751
 752         return 1;
 753 }
 754
 755 /*
 756  * Set active[i] to 1 if the dimension at position i is involved
 757  * in the linear expression l.
 758  */
 759 int *isl_local_space_get_active(__isl_keep isl_local_space *ls, isl_int *l)
 760 {
 761         int i, j;
 762         isl_ctx *ctx;
 763         int *active = NULL;
 764         unsigned total;
 765         unsigned offset;
 766
 767         ctx = isl_local_space_get_ctx(ls);
 768         total = isl_local_space_dim(ls, isl_dim_all);
 769         active = isl_calloc_array(ctx, int, total);
 770         if (!active)
 771                 return NULL;
 772
 773         for (i = 0; i < total; ++i)
 774                 active[i] = !isl_int_is_zero(l[i]);
 775
 776         offset = isl_local_space_offset(ls, isl_dim_div) - 1;
 777         for (i = ls->div->n_row - 1; i >= 0; --i) {
 778                 if (!active[offset + i])
 779                         continue;
 780                 for (j = 0; j < total; ++j)
 781                         active[j] |= !isl_int_is_zero(ls->div->row[i][2 + j]);
 782         }
 783
 784         return active;
 785 }