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 int isl_constraint_is_equality(struct isl_constraint *constraint)
 242 {
 243         if (!constraint)
 244                 return -1;
 245         return constraint->line < constraint->bmap->eq + constraint->bmap->n_eq;
 246 }
 247
 248
 249 struct isl_basic_set *isl_basic_set_from_constraint(
 250         struct isl_constraint *constraint)
 251 {
 252         int k;
 253         struct isl_basic_set *constraint_bset, *bset;
 254         isl_int *c;
 255         unsigned dim;
 256         unsigned nparam;
 257         unsigned total;
 258
 259         if (!constraint)
 260                 return NULL;
 261
 262         isl_assert(constraint->ctx,n(constraint, isl_dim_in) == 0, goto error);
 263
 264         constraint_bset = (struct isl_basic_set *)constraint->bmap;
 265         bset = isl_basic_set_universe_like(constraint_bset);
 266         bset = isl_basic_set_align_divs(bset, constraint_bset);
 267         nparam = isl_basic_set_n_param(bset);
 268         dim = isl_basic_set_n_dim(bset);
 269         bset = isl_basic_set_extend(bset, nparam, dim, 0, 1, 1);
 270         if (isl_constraint_is_equality(constraint)) {
 271                 k = isl_basic_set_alloc_equality(bset);
 272                 if (k < 0)
 273                         goto error;
 274                 c = bset->eq[k];
 275         }
 276         else {
 277                 k = isl_basic_set_alloc_inequality(bset);
 278                 if (k < 0)
 279                         goto error;
 280                 c = bset->ineq[k];
 281         }
 282         total = isl_basic_set_total_dim(bset);
 283         isl_seq_cpy(c, constraint->line[0], 1 + total);
 284         isl_constraint_free(constraint);
 285         return bset;
 286 error:
 287         isl_constraint_free(constraint);
 288         isl_basic_set_free(bset);
 289         return NULL;
 290 }
 291
 292 int isl_basic_set_has_defining_equality(
 293         struct isl_basic_set *bset, int pos,
 294         struct isl_constraint **c)
 295 {
 296         int i;
 297         unsigned dim, nparam;
 298
 299         if (!bset)
 300                 return -1;
 301         nparam = isl_basic_set_n_param(bset);
 302         dim = isl_basic_set_n_dim(bset);
 303         isl_assert(bset->ctx, pos < dim, return -1);
 304         for (i = 0; i < bset->n_eq; ++i)
 305                 if (!isl_int_is_zero(bset->eq[i][1 + nparam + pos]) &&
 306                     isl_seq_first_non_zero(bset->eq[i]+1+nparam+pos+1,
 307                                            dim-pos-1) == -1) {
 308                         *c= isl_basic_set_constraint(isl_basic_set_copy(bset),
 309                                                                 &bset->eq[i]);
 310                         return 1;
 311                 }
 312         return 0;
 313 }
 314
 315 int isl_basic_set_has_defining_inequalities(
 316         struct isl_basic_set *bset, int pos,
 317         struct isl_constraint **lower,
 318         struct isl_constraint **upper)
 319 {
 320         int i, j;
 321         unsigned dim;
 322         unsigned nparam;
 323         unsigned total;
 324         isl_int m;
 325         isl_int **lower_line, **upper_line;
 326
 327         if (!bset)
 328                 return -1;
 329         nparam = isl_basic_set_n_param(bset);
 330         dim = isl_basic_set_n_dim(bset);
 331         total = isl_basic_set_total_dim(bset);
 332         isl_assert(bset->ctx, pos < dim, return -1);
 333         isl_int_init(m);
 334         for (i = 0; i < bset->n_ineq; ++i) {
 335                 if (isl_int_is_zero(bset->ineq[i][1 + nparam + pos]))
 336                         continue;
 337                 if (isl_int_is_one(bset->ineq[i][1 + nparam + pos]))
 338                         continue;
 339                 if (isl_int_is_negone(bset->ineq[i][1 + nparam + pos]))
 340                         continue;
 341                 if (isl_seq_first_non_zero(bset->ineq[i]+1+nparam+pos+1,
 342                                                 dim-pos-1) != -1)
 343                         continue;
 344                 for (j = i + i; j < bset->n_ineq; ++j) {
 345                         if (!isl_seq_is_neg(bset->ineq[i]+1, bset->ineq[j]+1,
 346                                             total))
 347                                 continue;
 348                         isl_int_add(m, bset->ineq[i][0], bset->ineq[j][0]);
 349                         if (isl_int_abs_ge(m, bset->ineq[i][1+nparam+pos]))
 350                                 continue;
 351
 352                         if (isl_int_is_pos(bset->ineq[i][1+nparam+pos])) {
 353                                 lower_line = &bset->ineq[i];
 354                                 upper_line = &bset->ineq[j];
 355                         } else {
 356                                 lower_line = &bset->ineq[j];
 357                                 upper_line = &bset->ineq[i];
 358                         }
 359                         *lower = isl_basic_set_constraint(
 360                                         isl_basic_set_copy(bset), lower_line);
 361                         *upper = isl_basic_set_constraint(
 362                                         isl_basic_set_copy(bset), upper_line);
 363                         isl_int_clear(m);
 364                         return 1;
 365                 }
 366         }
 367         *lower = NULL;
 368         *upper = NULL;
 369         isl_int_clear(m);
 370         return 0;
 371 }