isl_constraint.c

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