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