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_constraint_dup(struct isl_constraint *c)
  58 {
  59         if (!c)
  60                 return NULL;
  61
  62         return isl_basic_map_constraint(isl_basic_map_copy(c->bmap), c->line);
  63 }
  64
  65 struct isl_constraint *isl_constraint_cow(struct isl_constraint *c)
  66 {
  67         if (!c)
  68                 return NULL;
  69
  70         if (c->ref == 1)
  71                 return c;
  72         c->ref--;
  73         return isl_constraint_dup(c);
  74 }
  75
  76 struct isl_constraint *isl_constraint_copy(struct isl_constraint *constraint)
  77 {
  78         if (!constraint)
  79                 return NULL;
  80
  81         constraint->ref++;
  82         return constraint;
  83 }
  84
  85 struct isl_constraint *isl_constraint_free(struct isl_constraint *c)
  86 {
  87         if (!c)
  88                 return;
  89
  90         if (--c->ref > 0)
  91                 return;
  92
  93         isl_basic_map_free(c->bmap);
  94         isl_ctx_deref(c->ctx);
  95         free(c);
  96 }
  97
  98 struct isl_constraint *isl_basic_set_first_constraint(
  99         struct isl_basic_set *bset)
 100 {
 101         struct isl_constraint *c;
 102
 103         if (!bset)
 104                 return NULL;
 105
 106         if (bset->n_eq > 0)
 107                 return isl_basic_set_constraint(bset, &bset->eq[0]);
 108
 109         if (bset->n_ineq > 0)
 110                 return isl_basic_set_constraint(bset, &bset->ineq[0]);
 111
 112         isl_basic_set_free(bset);
 113         return NULL;
 114 }
 115
 116 struct isl_constraint *isl_constraint_next(struct isl_constraint *c)
 117 {
 118         c = isl_constraint_cow(c);
 119         c->line++;
 120         if (c->line >= c->bmap->eq + c->bmap->n_eq && c->line < c->bmap->ineq)
 121                 c->line = c->bmap->ineq;
 122         if (c->line < c->bmap->ineq + c->bmap->n_ineq)
 123                 return c;
 124         isl_constraint_free(c);
 125         return NULL;
 126 }
 127
 128 int isl_constraint_is_equal(struct isl_constraint *constraint1,
 129         struct isl_constraint *constraint2)
 130 {
 131         if (!constraint1 || !constraint2)
 132                 return 0;
 133         return constraint1->bmap == constraint2->bmap &&
 134                constraint1->line == constraint2->line;
 135 }
 136
 137 int isl_constraint_dim(struct isl_constraint *constraint,
 138         enum isl_dim_type type)
 139 {
 140         if (!constraint)
 141                 return -1;
 142         return n(constraint, type);
 143 }
 144
 145 void isl_constraint_get_constant(struct isl_constraint *constraint, isl_int *v)
 146 {
 147         if (!constraint)
 148                 return;
 149         isl_int_set(*v, constraint->line[0][0]);
 150 }
 151
 152 void isl_constraint_get_coefficient(struct isl_constraint *constraint,
 153         enum isl_dim_type type, int pos, isl_int *v)
 154 {
 155         if (!constraint)
 156                 return;
 157
 158         isl_assert(constraint->ctx, pos < n(constraint, type), return);
 159         isl_int_set(*v, constraint->line[0][offset(constraint, type) + pos]);
 160 }
 161
 162 void isl_constraint_set_constant(struct isl_constraint *constraint, isl_int v)
 163 {
 164         if (!constraint)
 165                 return;
 166         isl_int_set(constraint->line[0][0], v);
 167 }
 168
 169 void isl_constraint_set_coefficient(struct isl_constraint *constraint,
 170         enum isl_dim_type type, int pos, isl_int v)
 171 {
 172         if (!constraint)
 173                 return;
 174
 175         isl_assert(constraint->ctx, pos < n(constraint, type), return);
 176         isl_int_set(constraint->line[0][offset(constraint, type) + pos], v);
 177 }
 178
 179 void isl_constraint_clear(struct isl_constraint *constraint)
 180 {
 181         struct isl_basic_set *bset;
 182         unsigned total;
 183
 184         if (!constraint)
 185                 return;
 186         total = isl_basic_map_total_dim(constraint->bmap);
 187         isl_seq_clr(constraint->line[0], 1 + total);
 188 }
 189
 190 int isl_constraint_is_equality(struct isl_constraint *constraint)
 191 {
 192         if (!constraint)
 193                 return -1;
 194         return constraint->line < constraint->bmap->eq + constraint->bmap->n_eq;
 195 }
 196
 197
 198 struct isl_basic_set *isl_basic_set_from_constraint(
 199         struct isl_constraint *constraint)
 200 {
 201         int k;
 202         struct isl_basic_set *constraint_bset, *bset;
 203         isl_int *c;
 204         unsigned dim;
 205         unsigned nparam;
 206         unsigned total;
 207
 208         if (!constraint)
 209                 return NULL;
 210
 211         isl_assert(constraint->ctx,n(constraint, isl_dim_in) == 0, goto error);
 212
 213         constraint_bset = (struct isl_basic_set *)constraint->bmap;
 214         bset = isl_basic_set_universe_like(constraint_bset);
 215         bset = isl_basic_set_align_divs(bset, constraint_bset);
 216         nparam = isl_basic_set_n_param(bset);
 217         dim = isl_basic_set_n_dim(bset);
 218         bset = isl_basic_set_extend(bset, nparam, dim, 0, 1, 1);
 219         if (isl_constraint_is_equality(constraint)) {
 220                 k = isl_basic_set_alloc_equality(bset);
 221                 if (k < 0)
 222                         goto error;
 223                 c = bset->eq[k];
 224         }
 225         else {
 226                 k = isl_basic_set_alloc_inequality(bset);
 227                 if (k < 0)
 228                         goto error;
 229                 c = bset->ineq[k];
 230         }
 231         total = isl_basic_set_total_dim(bset);
 232         isl_seq_cpy(c, constraint->line[0], 1 + total);
 233         isl_constraint_free(constraint);
 234         return bset;
 235 error:
 236         isl_constraint_free(constraint);
 237         isl_basic_set_free(bset);
 238         return NULL;
 239 }
 240
 241 int isl_basic_set_has_defining_equality(
 242         struct isl_basic_set *bset, int pos,
 243         struct isl_constraint **c)
 244 {
 245         int i;
 246         unsigned dim, nparam;
 247
 248         if (!bset)
 249                 return -1;
 250         nparam = isl_basic_set_n_param(bset);
 251         dim = isl_basic_set_n_dim(bset);
 252         isl_assert(bset->ctx, pos < dim, return -1);
 253         for (i = 0; i < bset->n_eq; ++i)
 254                 if (!isl_int_is_zero(bset->eq[i][1 + nparam + pos]) &&
 255                     isl_seq_first_non_zero(bset->eq[i]+1+nparam+pos+1,
 256                                            dim-pos-1) == -1) {
 257                         *c= isl_basic_set_constraint(isl_basic_set_copy(bset),
 258                                                                 &bset->eq[i]);
 259                         return 1;
 260                 }
 261         return 0;
 262 }
 263
 264 int isl_basic_set_has_defining_inequalities(
 265         struct isl_basic_set *bset, int pos,
 266         struct isl_constraint **lower,
 267         struct isl_constraint **upper)
 268 {
 269         int i, j;
 270         unsigned dim;
 271         unsigned nparam;
 272         unsigned total;
 273         isl_int m;
 274         isl_int **lower_line, **upper_line;
 275
 276         if (!bset)
 277                 return -1;
 278         nparam = isl_basic_set_n_param(bset);
 279         dim = isl_basic_set_n_dim(bset);
 280         total = isl_basic_set_total_dim(bset);
 281         isl_assert(bset->ctx, pos < dim, return -1);
 282         isl_int_init(m);
 283         for (i = 0; i < bset->n_ineq; ++i) {
 284                 if (isl_int_is_zero(bset->ineq[i][1 + nparam + pos]))
 285                         continue;
 286                 if (isl_int_is_one(bset->ineq[i][1 + nparam + pos]))
 287                         continue;
 288                 if (isl_int_is_negone(bset->ineq[i][1 + nparam + pos]))
 289                         continue;
 290                 if (isl_seq_first_non_zero(bset->ineq[i]+1+nparam+pos+1,
 291                                                 dim-pos-1) != -1)
 292                         continue;
 293                 for (j = i + i; j < bset->n_ineq; ++j) {
 294                         if (!isl_seq_is_neg(bset->ineq[i]+1, bset->ineq[j]+1,
 295                                             total))
 296                                 continue;
 297                         isl_int_add(m, bset->ineq[i][0], bset->ineq[j][0]);
 298                         if (isl_int_abs_ge(m, bset->ineq[i][1+nparam+pos]))
 299                                 continue;
 300
 301                         if (isl_int_is_pos(bset->ineq[i][1+nparam+pos])) {
 302                                 lower_line = &bset->ineq[i];
 303                                 upper_line = &bset->ineq[j];
 304                         } else {
 305                                 lower_line = &bset->ineq[j];
 306                                 upper_line = &bset->ineq[i];
 307                         }
 308                         *lower = isl_basic_set_constraint(
 309                                         isl_basic_set_copy(bset), lower_line);
 310                         *upper = isl_basic_set_constraint(
 311                                         isl_basic_set_copy(bset), upper_line);
 312                         isl_int_clear(m);
 313                         return 1;
 314                 }
 315         }
 316         *lower = NULL;
 317         *upper = NULL;
 318         isl_int_clear(m);
 319         return 0;
 320 }