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         if (!c)
 107                 return NULL;
 108
 109         return isl_basic_map_constraint(isl_basic_map_copy(c->bmap), c->line);
 110 }
 111
 112 struct isl_constraint *isl_constraint_cow(struct isl_constraint *c)
 113 {
 114         if (!c)
 115                 return NULL;
 116
 117         if (c->ref == 1)
 118                 return c;
 119         c->ref--;
 120         return isl_constraint_dup(c);
 121 }
 122
 123 struct isl_constraint *isl_constraint_copy(struct isl_constraint *constraint)
 124 {
 125         if (!constraint)
 126                 return NULL;
 127
 128         constraint->ref++;
 129         return constraint;
 130 }
 131
 132 void isl_constraint_free(struct isl_constraint *c)
 133 {
 134         if (!c)
 135                 return;
 136
 137         if (--c->ref > 0)
 138                 return;
 139
 140         isl_basic_map_free(c->bmap);
 141         isl_ctx_deref(c->ctx);
 142         free(c);
 143 }
 144
 145 __isl_give isl_constraint *isl_basic_map_first_constraint(
 146         __isl_take isl_basic_map *bmap)
 147 {
 148         if (!bmap)
 149                 return NULL;
 150
 151         if (bmap->n_eq > 0)
 152                 return isl_basic_map_constraint(bmap, &bmap->eq[0]);
 153
 154         if (bmap->n_ineq > 0)
 155                 return isl_basic_map_constraint(bmap, &bmap->ineq[0]);
 156
 157         isl_basic_map_free(bmap);
 158         return NULL;
 159 }
 160
 161 __isl_give isl_constraint *isl_basic_set_first_constraint(
 162         __isl_take isl_basic_set *bset)
 163 {
 164         return isl_basic_map_first_constraint((struct isl_basic_map *)bset);
 165 }
 166
 167 struct isl_constraint *isl_constraint_next(struct isl_constraint *c)
 168 {
 169         c = isl_constraint_cow(c);
 170         if (c->line >= c->bmap->eq) {
 171                 c->line++;
 172                 if (c->line < c->bmap->eq + c->bmap->n_eq)
 173                         return c;
 174                 c->line = c->bmap->ineq;
 175         } else
 176                 c->line++;
 177         if (c->line < c->bmap->ineq + c->bmap->n_ineq)
 178                 return c;
 179         isl_constraint_free(c);
 180         return NULL;
 181 }
 182
 183 int isl_constraint_is_equal(struct isl_constraint *constraint1,
 184         struct isl_constraint *constraint2)
 185 {
 186         if (!constraint1 || !constraint2)
 187                 return 0;
 188         return constraint1->bmap == constraint2->bmap &&
 189                constraint1->line == constraint2->line;
 190 }
 191
 192 struct isl_basic_map *isl_basic_map_add_constraint(
 193         struct isl_basic_map *bmap, struct isl_constraint *constraint)
 194 {
 195         if (!bmap || !constraint)
 196                 goto error;
 197
 198         isl_assert(constraint->ctx,
 199                 isl_dim_equal(bmap->dim, constraint->bmap->dim), goto error);
 200
 201         bmap = isl_basic_map_intersect(bmap,
 202                                 isl_basic_map_from_constraint(constraint));
 203         return bmap;
 204 error:
 205         isl_basic_map_free(bmap);
 206         isl_constraint_free(constraint);
 207         return NULL;
 208 }
 209
 210 struct isl_basic_set *isl_basic_set_add_constraint(
 211         struct isl_basic_set *bset, struct isl_constraint *constraint)
 212 {
 213         return (struct isl_basic_set *)
 214                 isl_basic_map_add_constraint((struct isl_basic_map *)bset,
 215                                                 constraint);
 216 }
 217
 218 struct isl_constraint *isl_constraint_add_div(struct isl_constraint *constraint,
 219         struct isl_div *div, int *pos)
 220 {
 221         if (!constraint || !div)
 222                 goto error;
 223
 224         isl_assert(constraint->ctx,
 225             isl_dim_equal(div->bmap->dim, constraint->bmap->dim), goto error);
 226         isl_assert(constraint->ctx,
 227             constraint->bmap->n_eq + constraint->bmap->n_ineq == 1, goto error);
 228
 229         constraint->bmap = isl_basic_map_cow(constraint->bmap);
 230         constraint->bmap = isl_basic_map_extend_dim(constraint->bmap,
 231                                 isl_dim_copy(constraint->bmap->dim), 1, 0, 0);
 232         if (!constraint->bmap)
 233                 goto error;
 234         constraint->line = &constraint->bmap->eq[0];
 235         *pos = isl_basic_map_alloc_div(constraint->bmap);
 236         if (*pos < 0)
 237                 goto error;
 238         isl_seq_cpy(constraint->bmap->div[*pos], div->line[0],
 239                         1 + 1 + isl_basic_map_total_dim(constraint->bmap));
 240         isl_div_free(div);
 241         return constraint;
 242 error:
 243         isl_constraint_free(constraint);
 244         isl_div_free(div);
 245         return NULL;
 246 }
 247
 248 int isl_constraint_dim(struct isl_constraint *constraint,
 249         enum isl_dim_type type)
 250 {
 251         if (!constraint)
 252                 return -1;
 253         return n(constraint, type);
 254 }
 255
 256 void isl_constraint_get_constant(struct isl_constraint *constraint, isl_int *v)
 257 {
 258         if (!constraint)
 259                 return;
 260         isl_int_set(*v, constraint->line[0][0]);
 261 }
 262
 263 void isl_constraint_get_coefficient(struct isl_constraint *constraint,
 264         enum isl_dim_type type, int pos, isl_int *v)
 265 {
 266         if (!constraint)
 267                 return;
 268
 269         isl_assert(constraint->ctx, pos < n(constraint, type), return);
 270         isl_int_set(*v, constraint->line[0][offset(constraint, type) + pos]);
 271 }
 272
 273 struct isl_div *isl_constraint_div(struct isl_constraint *constraint, int pos)
 274 {
 275         if (!constraint)
 276                 return NULL;
 277
 278         isl_assert(constraint->ctx, pos < n(constraint, isl_dim_div),
 279                         return NULL);
 280         return isl_basic_map_div(isl_basic_map_copy(constraint->bmap), pos);
 281 }
 282
 283 void isl_constraint_set_constant(struct isl_constraint *constraint, isl_int v)
 284 {
 285         if (!constraint)
 286                 return;
 287         isl_int_set(constraint->line[0][0], v);
 288 }
 289
 290 void isl_constraint_set_coefficient(struct isl_constraint *constraint,
 291         enum isl_dim_type type, int pos, isl_int v)
 292 {
 293         if (!constraint)
 294                 return;
 295
 296         isl_assert(constraint->ctx, pos < n(constraint, type), return);
 297         isl_int_set(constraint->line[0][offset(constraint, type) + pos], v);
 298 }
 299
 300 void isl_constraint_clear(struct isl_constraint *constraint)
 301 {
 302         unsigned total;
 303
 304         if (!constraint)
 305                 return;
 306         total = isl_basic_map_total_dim(constraint->bmap);
 307         isl_seq_clr(constraint->line[0], 1 + total);
 308 }
 309
 310 struct isl_constraint *isl_constraint_negate(struct isl_constraint *constraint)
 311 {
 312         unsigned total;
 313
 314         if (!constraint)
 315                 return NULL;
 316
 317         isl_assert(constraint->ctx, !isl_constraint_is_equality(constraint),
 318                         goto error);
 319         isl_assert(constraint->ctx, constraint->bmap->ref == 1, goto error);
 320         total = isl_basic_map_total_dim(constraint->bmap);
 321         isl_seq_neg(constraint->line[0], constraint->line[0], 1 + total);
 322         isl_int_sub_ui(constraint->line[0][0], constraint->line[0][0], 1);
 323         ISL_F_CLR(constraint->bmap, ISL_BASIC_MAP_NORMALIZED);
 324         return constraint;
 325 error:
 326         isl_constraint_free(constraint);
 327         return NULL;
 328 }
 329
 330 int isl_constraint_is_equality(struct isl_constraint *constraint)
 331 {
 332         if (!constraint)
 333                 return -1;
 334         return constraint->line >= constraint->bmap->eq;
 335 }
 336
 337 __isl_give isl_basic_map *isl_basic_map_from_constraint(
 338         __isl_take isl_constraint *constraint)
 339 {
 340         int k;
 341         struct isl_basic_map *bmap;
 342         isl_int *c;
 343         unsigned total;
 344
 345         if (!constraint)
 346                 return NULL;
 347
 348         if (constraint->bmap->n_eq + constraint->bmap->n_ineq == 1) {
 349                 bmap = isl_basic_map_copy(constraint->bmap);
 350                 isl_constraint_free(constraint);
 351                 return bmap;
 352         }
 353
 354         bmap = isl_basic_map_universe_like(constraint->bmap);
 355         bmap = isl_basic_map_align_divs(bmap, constraint->bmap);
 356         bmap = isl_basic_map_cow(bmap);
 357         bmap = isl_basic_map_extend_constraints(bmap, 1, 1);
 358         if (isl_constraint_is_equality(constraint)) {
 359                 k = isl_basic_map_alloc_equality(bmap);
 360                 if (k < 0)
 361                         goto error;
 362                 c = bmap->eq[k];
 363         }
 364         else {
 365                 k = isl_basic_map_alloc_inequality(bmap);
 366                 if (k < 0)
 367                         goto error;
 368                 c = bmap->ineq[k];
 369         }
 370         total = isl_basic_map_total_dim(bmap);
 371         isl_seq_cpy(c, constraint->line[0], 1 + total);
 372         isl_constraint_free(constraint);
 373         return bmap;
 374 error:
 375         isl_constraint_free(constraint);
 376         isl_basic_map_free(bmap);
 377         return NULL;
 378 }
 379
 380 struct isl_basic_set *isl_basic_set_from_constraint(
 381         struct isl_constraint *constraint)
 382 {
 383         if (!constraint)
 384                 return NULL;
 385
 386         isl_assert(constraint->ctx,n(constraint, isl_dim_in) == 0, goto error);
 387         return (isl_basic_set *)isl_basic_map_from_constraint(constraint);
 388 error:
 389         isl_constraint_free(constraint);
 390         return NULL;
 391 }
 392
 393 int isl_basic_set_has_defining_equality(
 394         struct isl_basic_set *bset, enum isl_dim_type type, int pos,
 395         struct isl_constraint **c)
 396 {
 397         int i;
 398         unsigned offset;
 399         unsigned total;
 400
 401         if (!bset)
 402                 return -1;
 403         offset = basic_set_offset(bset, type);
 404         total = isl_basic_set_total_dim(bset);
 405         isl_assert(bset->ctx, pos < isl_basic_set_dim(bset, type), return -1);
 406         for (i = 0; i < bset->n_eq; ++i)
 407                 if (!isl_int_is_zero(bset->eq[i][offset + pos]) &&
 408                     isl_seq_first_non_zero(bset->eq[i]+offset+pos+1,
 409                                            1+total-offset-pos-1) == -1) {
 410                         *c= isl_basic_set_constraint(isl_basic_set_copy(bset),
 411                                                                 &bset->eq[i]);
 412                         return 1;
 413                 }
 414         return 0;
 415 }
 416
 417 int isl_basic_set_has_defining_inequalities(
 418         struct isl_basic_set *bset, enum isl_dim_type type, int pos,
 419         struct isl_constraint **lower,
 420         struct isl_constraint **upper)
 421 {
 422         int i, j;
 423         unsigned offset;
 424         unsigned total;
 425         isl_int m;
 426         isl_int **lower_line, **upper_line;
 427
 428         if (!bset)
 429                 return -1;
 430         offset = basic_set_offset(bset, type);
 431         total = isl_basic_set_total_dim(bset);
 432         isl_assert(bset->ctx, pos < isl_basic_set_dim(bset, type), return -1);
 433         isl_int_init(m);
 434         for (i = 0; i < bset->n_ineq; ++i) {
 435                 if (isl_int_is_zero(bset->ineq[i][offset + pos]))
 436                         continue;
 437                 if (isl_int_is_one(bset->ineq[i][offset + pos]))
 438                         continue;
 439                 if (isl_int_is_negone(bset->ineq[i][offset + pos]))
 440                         continue;
 441                 if (isl_seq_first_non_zero(bset->ineq[i]+offset+pos+1,
 442                                                 1+total-offset-pos-1) != -1)
 443                         continue;
 444                 for (j = i + 1; j < bset->n_ineq; ++j) {
 445                         if (!isl_seq_is_neg(bset->ineq[i]+1, bset->ineq[j]+1,
 446                                             total))
 447                                 continue;
 448                         isl_int_add(m, bset->ineq[i][0], bset->ineq[j][0]);
 449                         if (isl_int_abs_ge(m, bset->ineq[i][offset+pos]))
 450                                 continue;
 451
 452                         if (isl_int_is_pos(bset->ineq[i][offset+pos])) {
 453                                 lower_line = &bset->ineq[i];
 454                                 upper_line = &bset->ineq[j];
 455                         } else {
 456                                 lower_line = &bset->ineq[j];
 457                                 upper_line = &bset->ineq[i];
 458                         }
 459                         *lower = isl_basic_set_constraint(
 460                                         isl_basic_set_copy(bset), lower_line);
 461                         *upper = isl_basic_set_constraint(
 462                                         isl_basic_set_copy(bset), upper_line);
 463                         isl_int_clear(m);
 464                         return 1;
 465                 }
 466         }
 467         *lower = NULL;
 468         *upper = NULL;
 469         isl_int_clear(m);
 470         return 0;
 471 }