isl_constraint.c

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