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