isl_constraint.c

   1 /*
   2  * Copyright 2008-2009 Katholieke Universiteit Leuven
   3  *
   4  * Use of this software is governed by the GNU LGPLv2.1 license
   5  *
   6  * Written by Sven Verdoolaege, K.U.Leuven, Departement
   7  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
   8  */
   9
  10 #include <isl_constraint.h>
  11 #include "isl_seq.h"
  12 #include "isl_map_private.h"
  13
  14 static unsigned n(struct isl_constraint *c, enum isl_dim_type type)
  15 {
  16         return isl_basic_map_dim(c->bmap, type);
  17 }
  18
  19 static unsigned offset(struct isl_constraint *c, enum isl_dim_type type)
  20 {
  21         struct isl_dim *dim = c->bmap->dim;
  22         switch (type) {
  23         case isl_dim_param:     return 1;
  24         case isl_dim_in:        return 1 + dim->nparam;
  25         case isl_dim_out:       return 1 + dim->nparam + dim->n_in;
  26         case isl_dim_div:       return 1 + dim->nparam + dim->n_in + dim->n_out;
  27         }
  28 }
  29
  30 static unsigned basic_set_offset(struct isl_basic_set *bset,
  31                                                         enum isl_dim_type type)
  32 {
  33         struct isl_dim *dim = bset->dim;
  34         switch (type) {
  35         case isl_dim_param:     return 1;
  36         case isl_dim_in:        return 1 + dim->nparam;
  37         case isl_dim_out:       return 1 + dim->nparam + dim->n_in;
  38         case isl_dim_div:       return 1 + dim->nparam + dim->n_in + dim->n_out;
  39         }
  40 }
  41
  42 struct isl_constraint *isl_basic_map_constraint(struct isl_basic_map *bmap,
  43         isl_int **line)
  44 {
  45         struct isl_constraint *constraint;
  46
  47         if (!bmap || !line)
  48                 goto error;
  49
  50         constraint = isl_alloc_type(bmap->ctx, struct isl_constraint);
  51         if (!constraint)
  52                 goto error;
  53
  54         constraint->ctx = bmap->ctx;
  55         isl_ctx_ref(constraint->ctx);
  56         constraint->ref = 1;
  57         constraint->bmap = bmap;
  58         constraint->line = line;
  59
  60         return constraint;
  61 error:
  62         isl_basic_map_free(bmap);
  63         return NULL;
  64 }
  65
  66 struct isl_constraint *isl_basic_set_constraint(struct isl_basic_set *bset,
  67         isl_int **line)
  68 {
  69         return isl_basic_map_constraint((struct isl_basic_map *)bset, line);
  70 }
  71
  72 struct isl_constraint *isl_equality_alloc(struct isl_dim *dim)
  73 {
  74         struct isl_basic_map *bmap;
  75
  76         if (!dim)
  77                 return NULL;
  78
  79         bmap = isl_basic_map_alloc_dim(dim, 0, 1, 0);
  80         if (!bmap)
  81                 return NULL;
  82
  83         isl_basic_map_alloc_equality(bmap);
  84         isl_seq_clr(bmap->eq[0], 1 + isl_basic_map_total_dim(bmap));
  85         return isl_basic_map_constraint(bmap, &bmap->eq[0]);
  86 }
  87
  88 struct isl_constraint *isl_inequality_alloc(struct isl_dim *dim)
  89 {
  90         struct isl_basic_map *bmap;
  91
  92         if (!dim)
  93                 return NULL;
  94
  95         bmap = isl_basic_map_alloc_dim(dim, 0, 0, 1);
  96         if (!bmap)
  97                 return NULL;
  98
  99         isl_basic_map_alloc_inequality(bmap);
 100         isl_seq_clr(bmap->ineq[0], 1 + isl_basic_map_total_dim(bmap));
 101         return isl_basic_map_constraint(bmap, &bmap->ineq[0]);
 102 }
 103
 104 struct isl_constraint *isl_constraint_dup(struct isl_constraint *c)
 105 {
 106         struct isl_basic_map *bmap;
 107         int i;
 108         int eq;
 109
 110         if (!c)
 111                 return NULL;
 112
 113         eq = c->line < c->bmap->eq + c->bmap->n_eq;
 114         i = eq ? c->line - c->bmap->eq : c->line - c->bmap->ineq;
 115         bmap = isl_basic_map_copy(c->bmap);
 116         if (!bmap)
 117                 return NULL;
 118         return isl_basic_map_constraint(bmap, eq ? bmap->eq + i : bmap->ineq + i);
 119 }
 120
 121 struct isl_constraint *isl_constraint_cow(struct isl_constraint *c)
 122 {
 123         if (!c)
 124                 return NULL;
 125
 126         if (c->ref == 1)
 127                 return c;
 128         c->ref--;
 129         return isl_constraint_dup(c);
 130 }
 131
 132 struct isl_constraint *isl_constraint_copy(struct isl_constraint *constraint)
 133 {
 134         if (!constraint)
 135                 return NULL;
 136
 137         constraint->ref++;
 138         return constraint;
 139 }
 140
 141 void isl_constraint_free(struct isl_constraint *c)
 142 {
 143         if (!c)
 144                 return;
 145
 146         if (--c->ref > 0)
 147                 return;
 148
 149         isl_basic_map_free(c->bmap);
 150         isl_ctx_deref(c->ctx);
 151         free(c);
 152 }
 153
 154 __isl_give isl_constraint *isl_basic_map_first_constraint(
 155         __isl_take isl_basic_map *bmap)
 156 {
 157         if (!bmap)
 158                 return NULL;
 159
 160         if (bmap->n_eq > 0)
 161                 return isl_basic_map_constraint(bmap, &bmap->eq[0]);
 162
 163         if (bmap->n_ineq > 0)
 164                 return isl_basic_map_constraint(bmap, &bmap->ineq[0]);
 165
 166         isl_basic_map_free(bmap);
 167         return NULL;
 168 }
 169
 170 __isl_give isl_constraint *isl_basic_set_first_constraint(
 171         __isl_take isl_basic_set *bset)
 172 {
 173         return isl_basic_map_first_constraint((struct isl_basic_map *)bset);
 174 }
 175
 176 struct isl_constraint *isl_constraint_next(struct isl_constraint *c)
 177 {
 178         c = isl_constraint_cow(c);
 179         if (c->line >= c->bmap->eq) {
 180                 c->line++;
 181                 if (c->line < c->bmap->eq + c->bmap->n_eq)
 182                         return c;
 183                 c->line = c->bmap->ineq;
 184         } else
 185                 c->line++;
 186         if (c->line < c->bmap->ineq + c->bmap->n_ineq)
 187                 return c;
 188         isl_constraint_free(c);
 189         return NULL;
 190 }
 191
 192 int isl_basic_map_foreach_constraint(__isl_keep isl_basic_map *bmap,
 193         int (*fn)(__isl_take isl_constraint *c, void *user), void *user)
 194 {
 195         int i;
 196         struct isl_constraint *c;
 197
 198         if (!bmap)
 199                 return -1;
 200
 201         for (i = 0; i < bmap->n_eq; ++i) {
 202                 c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
 203                                                 &bmap->eq[i]);
 204                 if (!c)
 205                         return -1;
 206                 if (fn(c, user) < 0)
 207                         return -1;
 208         }
 209
 210         for (i = 0; i < bmap->n_ineq; ++i) {
 211                 c = isl_basic_map_constraint(isl_basic_map_copy(bmap),
 212                                                 &bmap->ineq[i]);
 213                 if (!c)
 214                         return -1;
 215                 if (fn(c, user) < 0)
 216                         return -1;
 217         }
 218
 219         return 0;
 220 }
 221
 222 int isl_basic_set_foreach_constraint(__isl_keep isl_basic_set *bset,
 223         int (*fn)(__isl_take isl_constraint *c, void *user), void *user)
 224 {
 225         return isl_basic_map_foreach_constraint((isl_basic_map *)bset, fn, user);
 226 }
 227
 228 int isl_constraint_is_equal(struct isl_constraint *constraint1,
 229         struct isl_constraint *constraint2)
 230 {
 231         if (!constraint1 || !constraint2)
 232                 return 0;
 233         return constraint1->bmap == constraint2->bmap &&
 234                constraint1->line == constraint2->line;
 235 }
 236
 237 struct isl_basic_map *isl_basic_map_add_constraint(
 238         struct isl_basic_map *bmap, struct isl_constraint *constraint)
 239 {
 240         if (!bmap || !constraint)
 241                 goto error;
 242
 243         isl_assert(constraint->ctx,
 244                 isl_dim_equal(bmap->dim, constraint->bmap->dim), goto error);
 245
 246         bmap = isl_basic_map_intersect(bmap,
 247                                 isl_basic_map_from_constraint(constraint));
 248         return bmap;
 249 error:
 250         isl_basic_map_free(bmap);
 251         isl_constraint_free(constraint);
 252         return NULL;
 253 }
 254
 255 struct isl_basic_set *isl_basic_set_add_constraint(
 256         struct isl_basic_set *bset, struct isl_constraint *constraint)
 257 {
 258         return (struct isl_basic_set *)
 259                 isl_basic_map_add_constraint((struct isl_basic_map *)bset,
 260                                                 constraint);
 261 }
 262
 263 struct isl_constraint *isl_constraint_add_div(struct isl_constraint *constraint,
 264         struct isl_div *div, int *pos)
 265 {
 266         if (!constraint || !div)
 267                 goto error;
 268
 269         isl_assert(constraint->ctx,
 270             isl_dim_equal(div->bmap->dim, constraint->bmap->dim), goto error);
 271         isl_assert(constraint->ctx,
 272             constraint->bmap->n_eq + constraint->bmap->n_ineq == 1, goto error);
 273
 274         constraint->bmap = isl_basic_map_cow(constraint->bmap);
 275         constraint->bmap = isl_basic_map_extend_dim(constraint->bmap,
 276                                 isl_dim_copy(constraint->bmap->dim), 1, 0, 0);
 277         if (!constraint->bmap)
 278                 goto error;
 279         constraint->line = &constraint->bmap->eq[0];
 280         *pos = isl_basic_map_alloc_div(constraint->bmap);
 281         if (*pos < 0)
 282                 goto error;
 283         isl_seq_cpy(constraint->bmap->div[*pos], div->line[0],
 284                         1 + 1 + isl_basic_map_total_dim(constraint->bmap));
 285         isl_div_free(div);
 286         return constraint;
 287 error:
 288         isl_constraint_free(constraint);
 289         isl_div_free(div);
 290         return NULL;
 291 }
 292
 293 int isl_constraint_dim(struct isl_constraint *constraint,
 294         enum isl_dim_type type)
 295 {
 296         if (!constraint)
 297                 return -1;
 298         return n(constraint, type);
 299 }
 300
 301 void isl_constraint_get_constant(struct isl_constraint *constraint, isl_int *v)
 302 {
 303         if (!constraint)
 304                 return;
 305         isl_int_set(*v, constraint->line[0][0]);
 306 }
 307
 308 void isl_constraint_get_coefficient(struct isl_constraint *constraint,
 309         enum isl_dim_type type, int pos, isl_int *v)
 310 {
 311         if (!constraint)
 312                 return;
 313
 314         isl_assert(constraint->ctx, pos < n(constraint, type), return);
 315         isl_int_set(*v, constraint->line[0][offset(constraint, type) + pos]);
 316 }
 317
 318 struct isl_div *isl_constraint_div(struct isl_constraint *constraint, int pos)
 319 {
 320         if (!constraint)
 321                 return NULL;
 322
 323         isl_assert(constraint->ctx, pos < n(constraint, isl_dim_div),
 324                         return NULL);
 325         isl_assert(constraint->ctx,
 326                 !isl_int_is_zero(constraint->bmap->div[pos][0]), return NULL);
 327         return isl_basic_map_div(isl_basic_map_copy(constraint->bmap), pos);
 328 }
 329
 330 void isl_constraint_set_constant(struct isl_constraint *constraint, isl_int v)
 331 {
 332         if (!constraint)
 333                 return;
 334         isl_int_set(constraint->line[0][0], v);
 335 }
 336
 337 void isl_constraint_set_coefficient(struct isl_constraint *constraint,
 338         enum isl_dim_type type, int pos, isl_int v)
 339 {
 340         if (!constraint)
 341                 return;
 342
 343         isl_assert(constraint->ctx, pos < n(constraint, type), return);
 344         isl_int_set(constraint->line[0][offset(constraint, type) + pos], v);
 345 }
 346
 347 void isl_constraint_clear(struct isl_constraint *constraint)
 348 {
 349         unsigned total;
 350
 351         if (!constraint)
 352                 return;
 353         total = isl_basic_map_total_dim(constraint->bmap);
 354         isl_seq_clr(constraint->line[0], 1 + total);
 355 }
 356
 357 struct isl_constraint *isl_constraint_negate(struct isl_constraint *constraint)
 358 {
 359         unsigned total;
 360
 361         if (!constraint)
 362                 return NULL;
 363
 364         isl_assert(constraint->ctx, !isl_constraint_is_equality(constraint),
 365                         goto error);
 366         isl_assert(constraint->ctx, constraint->bmap->ref == 1, goto error);
 367         total = isl_basic_map_total_dim(constraint->bmap);
 368         isl_seq_neg(constraint->line[0], constraint->line[0], 1 + total);
 369         isl_int_sub_ui(constraint->line[0][0], constraint->line[0][0], 1);
 370         ISL_F_CLR(constraint->bmap, ISL_BASIC_MAP_NORMALIZED);
 371         return constraint;
 372 error:
 373         isl_constraint_free(constraint);
 374         return NULL;
 375 }
 376
 377 int isl_constraint_is_equality(struct isl_constraint *constraint)
 378 {
 379         if (!constraint)
 380                 return -1;
 381         return constraint->line >= constraint->bmap->eq;
 382 }
 383
 384 __isl_give isl_basic_map *isl_basic_map_from_constraint(
 385         __isl_take isl_constraint *constraint)
 386 {
 387         int k;
 388         struct isl_basic_map *bmap;
 389         isl_int *c;
 390         unsigned total;
 391
 392         if (!constraint)
 393                 return NULL;
 394
 395         if (constraint->bmap->n_eq + constraint->bmap->n_ineq == 1) {
 396                 bmap = isl_basic_map_copy(constraint->bmap);
 397                 isl_constraint_free(constraint);
 398                 return bmap;
 399         }
 400
 401         bmap = isl_basic_map_universe_like(constraint->bmap);
 402         bmap = isl_basic_map_align_divs(bmap, constraint->bmap);
 403         bmap = isl_basic_map_cow(bmap);
 404         bmap = isl_basic_map_extend_constraints(bmap, 1, 1);
 405         if (isl_constraint_is_equality(constraint)) {
 406                 k = isl_basic_map_alloc_equality(bmap);
 407                 if (k < 0)
 408                         goto error;
 409                 c = bmap->eq[k];
 410         }
 411         else {
 412                 k = isl_basic_map_alloc_inequality(bmap);
 413                 if (k < 0)
 414                         goto error;
 415                 c = bmap->ineq[k];
 416         }
 417         total = isl_basic_map_total_dim(bmap);
 418         isl_seq_cpy(c, constraint->line[0], 1 + total);
 419         isl_constraint_free(constraint);
 420         return bmap;
 421 error:
 422         isl_constraint_free(constraint);
 423         isl_basic_map_free(bmap);
 424         return NULL;
 425 }
 426
 427 struct isl_basic_set *isl_basic_set_from_constraint(
 428         struct isl_constraint *constraint)
 429 {
 430         if (!constraint)
 431                 return NULL;
 432
 433         isl_assert(constraint->ctx,n(constraint, isl_dim_in) == 0, goto error);
 434         return (isl_basic_set *)isl_basic_map_from_constraint(constraint);
 435 error:
 436         isl_constraint_free(constraint);
 437         return NULL;
 438 }
 439
 440 int isl_basic_set_has_defining_equality(
 441         struct isl_basic_set *bset, enum isl_dim_type type, int pos,
 442         struct isl_constraint **c)
 443 {
 444         int i;
 445         unsigned offset;
 446         unsigned total;
 447
 448         if (!bset)
 449                 return -1;
 450         offset = basic_set_offset(bset, type);
 451         total = isl_basic_set_total_dim(bset);
 452         isl_assert(bset->ctx, pos < isl_basic_set_dim(bset, type), return -1);
 453         for (i = 0; i < bset->n_eq; ++i)
 454                 if (!isl_int_is_zero(bset->eq[i][offset + pos]) &&
 455                     isl_seq_first_non_zero(bset->eq[i]+offset+pos+1,
 456                                            1+total-offset-pos-1) == -1) {
 457                         *c= isl_basic_set_constraint(isl_basic_set_copy(bset),
 458                                                                 &bset->eq[i]);
 459                         return 1;
 460                 }
 461         return 0;
 462 }
 463
 464 int isl_basic_set_has_defining_inequalities(
 465         struct isl_basic_set *bset, enum isl_dim_type type, int pos,
 466         struct isl_constraint **lower,
 467         struct isl_constraint **upper)
 468 {
 469         int i, j;
 470         unsigned offset;
 471         unsigned total;
 472         isl_int m;
 473         isl_int **lower_line, **upper_line;
 474
 475         if (!bset)
 476                 return -1;
 477         offset = basic_set_offset(bset, type);
 478         total = isl_basic_set_total_dim(bset);
 479         isl_assert(bset->ctx, pos < isl_basic_set_dim(bset, type), return -1);
 480         isl_int_init(m);
 481         for (i = 0; i < bset->n_ineq; ++i) {
 482                 if (isl_int_is_zero(bset->ineq[i][offset + pos]))
 483                         continue;
 484                 if (isl_int_is_one(bset->ineq[i][offset + pos]))
 485                         continue;
 486                 if (isl_int_is_negone(bset->ineq[i][offset + pos]))
 487                         continue;
 488                 if (isl_seq_first_non_zero(bset->ineq[i]+offset+pos+1,
 489                                                 1+total-offset-pos-1) != -1)
 490                         continue;
 491                 for (j = i + 1; j < bset->n_ineq; ++j) {
 492                         if (!isl_seq_is_neg(bset->ineq[i]+1, bset->ineq[j]+1,
 493                                             total))
 494                                 continue;
 495                         isl_int_add(m, bset->ineq[i][0], bset->ineq[j][0]);
 496                         if (isl_int_abs_ge(m, bset->ineq[i][offset+pos]))
 497                                 continue;
 498
 499                         if (isl_int_is_pos(bset->ineq[i][offset+pos])) {
 500                                 lower_line = &bset->ineq[i];
 501                                 upper_line = &bset->ineq[j];
 502                         } else {
 503                                 lower_line = &bset->ineq[j];
 504                                 upper_line = &bset->ineq[i];
 505                         }
 506                         *lower = isl_basic_set_constraint(
 507                                         isl_basic_set_copy(bset), lower_line);
 508                         *upper = isl_basic_set_constraint(
 509                                         isl_basic_set_copy(bset), upper_line);
 510                         isl_int_clear(m);
 511                         return 1;
 512                 }
 513         }
 514         *lower = NULL;
 515         *upper = NULL;
 516         isl_int_clear(m);
 517         return 0;
 518 }